DIV CSS 佈局教程網

javascript 實現數組的「正態分布」排序問題
編輯:JavaScript基礎知識     

前幾天頂著將近 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 中測過,其他瀏覽器若有問題歡迎留言反饋。這東西難度不高,權當一份記錄,需要的時候翻出來用。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved