JavaScriptで2つの配列の共通要素（積集合）を求めるintersection関数の実装方法

はじめに

JavaScriptには、2つの配列が与えられたときに、それらの共通部分（積集合）を計算して返す組み込みのメソッドは用意されていません。そこで本記事では、共通する要素を任意の順序で含む配列を返す関数 intersection() を自前で実装する方法を解説します。重要なポイントとして、結果に含まれる各要素は、両方の配列に現れる回数だけ繰り返して含める必要があります。

具体例

たとえば、入力が以下の2つの配列だったとします。

arr1 = ['hello', 'world', 'how', 'are', 'you'];
arr2 = ['hey', 'world', 'can', 'you', 'rotate'];

この場合、期待される出力は次のようになります。

['world', 'you'];

アプローチの検討

もし配列があらかじめソート済みであれば、「双ポインタ（ツーポインター）」方式が有効です。両方のポインタをそれぞれの配列の先頭（0番目）に置き、値を比較しながら対応するポインタを進めていくことで、時間計算量 O(m+n)（m と n は各配列のサイズ）で処理できます。

しかし今回扱うのは未ソートの配列です。わざわざソートを実行すると O(m log m + n log n) のコストがかかるため、このアプローチを採るメリットはありません。そこで、シンプルに最初の配列の各値をもう一方の配列と順番に照合し、一致した要素を共通要素の配列に追加していく方法を採用します。

この素朴な照合方式では、時間計算量は O(n²) になります。ただし、片方の短い配列を基準にループを回すことで、無駄な比較を減らす工夫をしています。

実装コード

以下が実際のコードです。

arr1 = ['hello', 'world', 'how', 'are', 'you'];
arr2 = ['hey', 'world', 'can', 'you', 'rotate'];
const intersectElements = (arr1, arr2) => {
    const res = [];
    const { length: len1 } = arr1;
    const { length: len2 } = arr2;
    // 短い方の配列を基準にループすることで効率化
    const smaller = (len1 < len2 ? arr1 : arr2).slice();
    const bigger = (len1 >= len2 ? arr1 : arr2).slice();
    for(let i = 0; i < smaller.length; i++) {
        if(bigger.indexOf(smaller[i]) !== -1){
            res.push(smaller[i]);
            // 一致した要素をundefinedで置き換え、重複カウントを防止
            bigger.splice(bigger.indexOf(smaller[i]), 1, undefined);
        }
    };
    return res;
};
console.log(intersectElements(arr1, arr2));

このコードのポイントは、一致が見つかった際に splice() を使って元の配列側の要素を undefined に置き換えているところです。これにより、同じ要素が複数回マッチしても、正しく重複を排除できる仕組みになっています。

出力結果

コンソールには次のように出力されます。

[ 'world', 'you' ]

まとめ

未ソートの配列同士の共通要素を求める場合、ソートしてから双ポインタを使うよりも、短い配列を基準に線形探索する方がシンプルで効率的です。データ量が小規模な場合は O(n²) のアプローチでも十分実用的ですが、大規模なデータを扱う場合は Set や Map を活用して O(m+n) に最適化することも検討するとよいでしょう。