DIV CSS 佈局教程網

JavaScript 獲取兩個陣列交集的方法
編輯:JavaScript綜合知識     

求兩個陣列的交集(同時存在於兩邊的元素)是很實用的操作。本文介紹一種以雙指標技巧實作、時間複雜度為 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))。可依資料規模與是否已排序,選擇最適合的寫法。

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