DIV CSS 佈局教程網

JavaScript 求兩個陣列交集:O(n) 雙指標實作
編輯:關於JavaScript     

求交集是資料處理中很常見的操作。這裡介紹一個效率極佳的做法——前提是兩個陣列都已經排序完成。

/*
 * 求兩個已排序陣列的交集
 *
 * PARAMS
 *   a - 第一個陣列,必須已排序
 *   b - 第二個陣列,必須已排序
 *
 * NOTES
 *   時間複雜度為 O(n),其中 n = MIN(a.length, b.length)
 */
function arrayIntersection(a, b) {
  var ai = 0, bi = 0;
  var result = new Array();

  while (ai < a.length && bi < b.length) {
    if (a[ai] < b[bi]) {
      ai++;                       // a 的當前值較小,往後一格
    } else if (a[ai] > b[bi]) {
      bi++;                       // b 的當前值較小,往後一格
    } else {                      // 兩者相等,找到交集元素
      result.push(a[ai]);
      ai++;
      bi++;
    }
  }
  return result;
}

console.log(arrayIntersection([1, 2, 3], [2, 3, 4, 5, 6])); // [2, 3]

演算法原理

這就是經典的雙指標(two pointers)思維,和合併兩個有序 linked list 的做法一模一樣:

  1. 各自維護一個游標 ai、bi,從頭開始比。
  2. 哪一邊的值比較小,就把那個游標往前推一格——因為排序過了,較小的值不可能再出現在後方。
  3. 兩值相等時,就是交集元素,收進結果陣列,兩個游標同時前進。
  4. 任一陣列走完即停止。

相比「對每個元素做一次 indexOf」的暴力解法(O(n×m)),這裡每個元素最多被拜訪一次,因此是線性時間。

如果陣列還沒排序

實務上資料往往是未排序的,這時可以改用 Set 達到同樣的線性期待複雜度:

function intersect(a, b) {
  const setB = new Set(b);
  const seen = new Set();
  const result = [];
  for (const v of a) {
    if (setB.has(v) && !seen.has(v)) {
      seen.add(v);
      result.push(v);
    }
  }
  return result;
}
console.log(intersect([1, 2, 3], [2, 3, 4, 5, 6])); // [2, 3]

兩種思路各有適用場景:資料本來就有序(例如時間序列、已排序索引)時,雙指標最省記憶體;資料零散時,Set 實作更省事。

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