DIV CSS 佈局教程網

合併兩個有序陣列:為什麼該用雙指針而不是 concat 再排序
編輯:關於JavaScript     

有一道很經典的題目:如何把兩個已排序的陣列合併成一個有序陣列。難點不在寫得出來,而在寫得快。「已排序」這個前提條件是整題的關鍵,若無視它,就浪費了最有價值的信息。

版本一:簡單但沒效率

最直接的想法是用內建的 concat 之後再排序:

function concatSort(arrA, arrB){
  return arrA.concat(arrB).sort();
}

這個做法完全沒有利用「陣列本來就有序」這個前提。

順帶說一個值得釐清的事:為了確認 sort 到底用了什麼演算法,去看了 V8 引擎的實作,大致意思是陣列長度較短時使用插入排序,較長時使用快速排序(現代版本則是 TimSort)。這也糾正了自己長以來的誤解——一直以為 sort 用的是泡沫排序。

版本二:取小者插入(雙指針)

思路:同時遍歷兩個陣列,用兩個指標記錄各自走到哪裡,每次比較兩邊目前的值,把較小者放進結果陣列,然後把該指標往前推進一格,重複直到兩邊都走完。

function con(arrA, arrB){
  var i, j, k,
      lenA = arrA.length,
      lenB = arrB.length,
      allLen = lenA + lenB,
      result = [];

  for(i = 0, j = 0, k = 0; k < allLen; k++ ){
    if(i < lenA && (j >= lenB || arrA[i] < arrB[j])){
      result.push(arrA[i++]);
    }else{
      result.push(arrB[j++]);
    }
  }
  return result;
}

var a = [1,2,4], b = [3,5,6,7,10];
console.log(con(a,b)); // [1,2,3,4,5,6,7,10]

第一次寫的時候判斷條件寫錯了,結果進入無窮迴圈——這裡的邊界條件確實容易出錯,重點是 i < lenA 與 j >= lenB 兩個判斷的順序不能顛倒:必須先確認 A 還有剩,再看 B 是否已耗盡,否則讀到 undefined 就會出錯。

把這個版本與 concatSort 做效能比較,結果顯示雙指針明顯勝出。原因很直觀:concatSort 要做 n log n 次比較,而雙指針每個元素只比一次,是 O(n)。

問題升級:合併多個有序陣列

如果有 A = [1,5]、B = [2,6]、C = [3,4]……一直到 K,要求合併後的有序陣列呢?

當時被問到這個問題,第一感覺是很像「歸並排序」,但再一想,歸並排序用不上「每個子陣列已排序」這個前提。接著想到堆排序、快速排序,發現也無法有效利用這個條件,最後選擇放棄。面試結束後依然沒有頭緒。

回到宿舍的路上,師弟說了一句「又要過節了」——那個「又」字點醒了我:既然合併兩個很簡單,那就反覆合併就好了。

function conMore(){
  var outerArr = [], i, len = arguments.length, result = [];
  for(i = 0; i < len; i++){
    outerArr.push(arguments[i]);
  }
  if(result.length === 0){
    result = outerArr[0];
  }
  for(i = 1; i < len; i++){
    result = con(result, outerArr[i]); // 一次又一次地合併
  }
  return result;
}

var a = [1,4,7], b = [2,5,8], c = [3,6,9,10];
console.log(conMore(a,b,c)); // [1,2,3,4,5,6,7,8,9,10]

這個做法簡單可靠,時間複雜度是 O(k × n),其中 k 是陣列個數。它稱不上最快,但足夠好,而且程式碼幾行就寫完。

更進一步:若要更快

如果 k 很大,可以改用最小堆:把每個陣列的第一個元素放進堆,每次取出最小值放入結果,再把該元素所在陣列的下一個元素補進堆。時間複雜度是 O(n log k),比反覆合併好。

另一個思路是分治合併:把 k 個陣列兩兩配對合併,再把合併出來的結果兩兩配對,像錦標賽一樣。log k 回合之後就得到答案,同樣是 O(n log k),但實作比堆簡單。

這個過程也說明了一件重要的事:面試時卡住不代表能力不行。 雙指針的邊界條件、多陣列合併的策略選擇,都是需要練習才會熟悉的模式。事後把最佳解法補起來,下一次就會了。

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