萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 獲取兩個有序數組交集:O(n) 雙指針算法實現

前言

獲取兩個數組交集是常見算法題。當數組已排序時,雙指針法可在 O(n+m) 時間、O(1) 額外空間 (不計結果數組) 解決。本文詳細講解算法邏輯、代碼實現、邊界處理及擴展場景。

一、算法核心邏輯

利用兩個數組已排序的特性,雙指針同步遍歷:

  • 指針 ai 指向數組 a,bi 指向 b
  • 比較 a[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]

三、關鍵細節處理

1. 重複元素處理

上述代碼保留重複:若 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;
}

2. 未排序數組預處理


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));
}

3. 泛型比較函數支持


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))
穩定性穩定 (保持順序)無序 (需額外排序)
前置條件必須已排序無

五、實戰應用場景

  • 倒排索引合併 (搜索引擎核心操作)
  • 日誌分析:找出同時出現在兩個日誌中的用戶 ID
  • 數據去重合併:多源數據同步
  • 權限系統:用戶角色與資源權限交集

六、完整代碼示例


/* 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 方案編碼更簡單、性能同階,但需額外空間。根據數據特徵選擇合適方案。

copyright © 萬盛學電腦網 all rights reserved