JavaScriptで重複要素を含む2つの配列の共通部分を効率的に求める方法

はじめに

JavaScriptでは、2つの数値配列(arr1とarr2)を受け取り、それらに共通するすべての要素を集めた新しい配列を作成する関数が必要になることがあります。

ここで重要なのは、同一の要素が両方の配列に複数回存在する場合、その出現回数分だけすべてのインスタンスを結果に含めなければならないという点です。単純な重複排除型の積集合とは異なり、各要素の出現の出現頻度を正しく扱う必要があります。

入力例と期待される出力

const arr1 = [1, 2, 2, 4, 4, 5, 6];
const arr2 = [3, 2, 4, 2, 4, 9];

この場合、出力は次のようになります。

const output = [2, 2, 4, 4];

2と4はそれぞれ両方の配列に2回ずつ現れているため、結果にも2回ずつ含まれています。

実装方法

この問題を効率的に解くには、Mapオブジェクトを使ってarr2内の各要素の出現回数をあらかじめカウントしておき、その後arr1を走査しながら対応するカウントを減らしていくアプローチが有効です。

const arr1 = [1, 2, 2, 4, 4, 5, 6];
const arr2 = [3, 2, 4, 2, 4, 9];

const findIntersection = (arr1 = [], arr2 = []) => {
    // arr2 の各要素の出現回数を Map に記録
    const map = new Map();
    for (const el of arr2) {
        const count = map.get(el) || 0;
        map.set(el, count + 1);
    }

    // arr1 を走査し、Map にカウントが残っている要素だけを抽出
    return arr1.filter(el => {
        let count = map.get(el);
        if (count) {
            map.set(el, --count);
            return true;
        }
        return false;
    });
};

console.log(findIntersection(arr1, arr2));

出力結果

コンソールには以下が出力されます。

[2, 2, 4, 4]

コードの解説

処理の流れは大きく分けて2段階です。

ステップ1: まず、arr2の各要素をループで走査し、Mapのキーとして要素の値、値として出現回数を保存します。

ステップ2: 次に、arr1に対してfilter()を実行します。各要素についてMapにカウントが残っている場合はtrueを返すと同時にカウントを1減らします。これにより、出現回数が一致した共通部分だけが新しい配列として返されます。

この手法の計算量はO(n + m)(nとmはそれぞれの配列の長さ)であり、ネストしたループを使う素朴な実装(O(n × m))よりも大幅に高速です。特に大きな配列同士を比較する場合に、その効果を実感できるでしょう。