求交集是資料處理中很常見的操作。這裡介紹一個效率極佳的做法——前提是兩個陣列都已經排序完成。
/*
* 求兩個已排序陣列的交集
*
* 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 的做法一模一樣:
ai、bi,從頭開始比。相比「對每個元素做一次 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 實作更省事。