獲取兩個數組交集是常見算法題。當數組已排序時,雙指針法可在 O(n+m) 時間、O(1) 額外空間 (不計結果數組) 解決。本文詳細講解算法邏輯、代碼實現、邊界處理及擴展場景。
利用兩個數組已排序的特性,雙指針同步遍歷:
ai 指向數組 a,bi 指向 ba[ai] 和 b[bi]:
a[ai] < b[bi] → ai++ (a 較小,前進)a[ai] > b[bi] → bi++ (b 較小,前進)相等 → 加入結果,ai++、bi++
/**
* 獲取兩個已排序數組的交集
* @param {Array} a - 第一個已排序數組
* @param {Array} b - 第二個已排序數組
* @returns {Array} 交集數組 (保持排序、去重取決於邏輯)
*/
function arrayIntersection(a, b) {
let ai = 0, bi = 0;
const result = [];
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]
上述代碼保留重複:若 a=[2,2,3], b=[2,3,3] → 結果 [2,3]。
若需去重 (集合交集):
function arrayIntersectionUnique(a, b) {
let ai = 0, bi = 0;
const result = [];
while (ai < a.length && bi < b.length) {
if (a[ai] < b[bi]) ai++;
else if (a[ai] > b[bi]) bi++;
else {
// 去重:結果為空或不等於最後添加的值
if (result.length === 0 || result[result.length-1] !== a[ai]) {
result.push(a[ai]);
}
ai++; bi++;
}
}
return result;
}
function intersectionUnsorted(a, b) {
// 方案一:排序後雙指針 O(n log n + m log m)
return arrayIntersection([...a].sort((x,y)=>x-y), [...b].sort((x,y)=>x-y));
// 方案二:Set 查找 O(n+m) 空間 O(min(n,m))
// const set = new Set(a.length < b.length ? a : b);
// return [...new Set(b.length < a.length ? b : a)].filter(x => set.has(x));
}
function arrayIntersectionBy(a, b, compareFn = (x,y) => x-y, keyFn = x=>x) {
let ai = 0, bi = 0;
const result = [];
while (ai < a.length && bi < b.length) {
const cmp = compareFn(keyFn(a[ai]), keyFn(b[bi]));
if (cmp < 0) ai++;
else if (cmp > 0) bi++;
else {
result.push(a[ai]); // 或 b[bi]
ai++; bi++;
}
}
return result;
}
// 對象數組按 id 交集
const a = [{id:1}, {id:2}, {id:3}];
const b = [{id:2}, {id:3}, {id:4}];
console.log(arrayIntersectionBy(a, b, (x,y)=>x-y, o=>o.id)); // [{id:2}, {id:3}]
| 指標 | 雙指針 (已排序) | Set/Hash (未排序) |
|---|---|---|
| 時間複雜度 | O(n + m) | O(n + m) |
| 空間複雜度 | O(1) (不計結果) | O(min(n,m)) |
| 穩定性 | 穩定 (保持順序) | 無序 (需額外排序) |
| 前置條件 | 必須已排序 | 無 |
/* finds the intersection of
* two arrays in a simple fashion.
* PARAMS
* a - first array, must already be sorted
* b - second array, must already be sorted
* NOTES
* Should have O(n) operations, where n is 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]
雙指針法是有序數組交集的最優解法,時間線性、空間常數、代碼簡潔。關鍵前提是數組必須預排序。未排序場景下,Set 方案編碼更簡單、性能同階,但需額外空間。根據數據特徵選擇合適方案。