求兩個陣列的交集(同時存在於兩邊的元素)是很實用的操作。本文介紹一種以雙指標技巧實作、時間複雜度為 O(n) 的方法,前提是傳入的兩個陣列都必須「已排序」。
/* 求兩個已排序陣列的交集
* a - 第一個陣列,必須已排序
* b - 第二個陣列,必須已排序
* 時間複雜度約為 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++;
} else if (a[ai] > b[bi]){
bi++;
} else { // 兩者相等,即為交集元素
result.push(a[ai]);
ai++;
bi++;
}
}
return result;
}
console.log(arrayIntersection([1, 2, 3], [2, 3, 4, 5, 6])); // [2, 3]
演算法用 ai、bi 兩個指標分別指向兩個陣列的当前位置,比較所指元素:較小的一方指標前進,兩者相等時就把它收進結果並同時前進。因為只走一遍、且每次至少前進一個指標,所以時間複雜度為 O(n)。
若陣列尚未排序,可先呼叫 sort() 排序再套用此法;或使用 ES6 的 Set 搭配 filter 來求交集:a.filter(x => new Set(b).has(x))。可依資料規模與是否已排序,選擇最適合的寫法。