前幾天頂著將近 40 度的天氣四處面試,每次回來都汗流浹背。過程中遇到幾道筆試題,其中一道因為實際工作裡沒碰過,印象比較深:
給定 var arr = [1,2,1,3,3,2,4,6,3],把它整理成正態分布的形狀,也就是 [1,2,3,3,6,4,3,2,1]。
所謂正態分布,看處理後的數組就能明白:兩頭小、中間大,畫到坐標軸上就是那條鐘形曲線——左低右低、中間高、左右對稱,所以也常被稱為鐘形曲線。
這是最後一題,時間緊、天氣熱、又渴又餓(好吧,主要就是算法功底不夠),匆匆寫了:
var arr = [1, 2, 1, 3, 3, 2, 4, 6, 3];
~(function (arr) {
var temp = [], i = 0, l = arr.length;
// 先從小到大排序:[1, 1, 2, 2, 3, 3, 3, 4, 6]
var sortArr = arr.sort(function (a, b) { return a - b; });
for (; i < l; i++) {
if (i % 2 == 0) {
temp[i / 2] = sortArr[i]; // 偶數下標順序放左半邊
} else {
temp[l - (i + 1) / 2] = sortArr[i]; // 奇數下標倒序放右半邊
}
}
console.log(temp); // [1, 2, 3, 3, 6, 4, 3, 2, 1]
})(arr);
看著挺完美,面試官事後也沒就此提問,我以為過關了。可回程路上我突然想到另一種情況:
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]; // 規律遞增
~(function (arr) {
var temp = [], i = 0, l = arr.length;
var sortArr = arr.sort(function (a, b) { return a - b; });
for (; i < l; i++) {
if (i % 2 == 0) {
temp[i / 2] = sortArr[i];
} else {
temp[l - (i + 1) / 2] = sortArr[i];
}
}
console.log(temp); // [1, 3, 5, 7, 9, 8, 6, 4, 2]
})(arr);
左右兩側並不對稱了:以 9 為中心,左側 1+3+5+7=16,右側 2+4+6+8=20,明顯左輕右重。數組越長,這種傾斜就越嚴重。顯然不能算合格的正態分布。
問題的核心是讓左右兩半的總量盡量接近。無論元素個數是奇是偶都可以拆成兩部分(奇數時去掉最大值後即為偶數,即使有多個相同的最大值也無妨,排序後丟掉最後一個即可)。仍然按奇偶下標分置左右,但在兩側長度相等時比較一次和:由於是升序填充,右側通常會偏大,此時把右側的第一個與左側的最後一個交換即可。
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
var sortArr = arr.sort(function (a, b) { return a - b; });
var l = arr.length;
var temp_left = [], temp_right = [];
function sort(arr) {
var i = 0;
for (; i < l; i++) {
var eq = sortArr[i];
i % 2 == 0 ? temp_left.push(eq) : temp_right.unshift(eq);
if (i > 1) {
// 兩側長度相等且右側和更大時進行交換
if (temp_left.length == temp_right.length && !compare(temp_left, temp_right)) {
wrap(temp_left, temp_right);
}
}
}
return temp_left.concat(temp_right);
}
// 數組求和
function sum(arr) {
return eval(arr.join("+"));
}
// 比較兩側大小
function compare(arr1, arr2) {
return sum(arr1) >= sum(arr2);
}
// 左側最後一個與右側第一個交換
function wrap(l, r) {
var m = r.shift();
r.unshift(l.pop());
l.push(m);
}
console.log(sort(arr)); // [1, 4, 6, 7, 9, 8, 5, 3, 2]
再跑幾組數據看看:
arr = [1, 333, 444, 555, 66, 7788, 909]; console.log(sort(arr)); // [1, 444, 909, 7788, 555, 333, 66] arr = [168.6, 177.5, 174.2, 189.3, 167.2, 177.6, 167.8, 175.5]; console.log(sort(arr)); // [167.2, 174.2, 175.5, 189.3, 177.6, 177.5, 168.6, 167.8]
左右均衡多了。網上還能找到用 C++ 實現的版本,但那篇文末給出的結果並不是均勻的正態分布,反而和最初的初版思路接近。我不太寫 C++,沒有批量跑對比,感興趣的同學可以自己驗證一下。
本文所有程序只在 Chrome 中測過,其他瀏覽器若有問題歡迎留言反饋。這東西難度不高,權當一份記錄,需要的時候翻出來用。