JavaScriptで2つの配列の共通要素を取得する方法（重複要素も保持）

問題

2つの配列 arr1 と arr2 をそれぞれ第1引数・第2引数として受け取る JavaScript の関数を作成する必要があります。

この関数は、両方の配列に共通して存在する要素（積集合）を求めます。さらに、ある要素が両方の配列に2回登場する場合には、結果の配列にもその要素を2回含めなければなりません。

例えば、関数への入力が次のような場合です。

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

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

const output = [7, 7, 4];

7 と 4 はどちらも両方の配列に存在し、7 はそれぞれの配列で2回出現しているため、結果にも2回含まれています。

実装例

この問題を解くコードは以下のとおりです。

const arr1 = [2, 7, 4, 6, 7, 4];
const arr2 = [7, 1, 9, 7, 4, 5];
const intersect = (arr1 = [], arr2 = []) => {
    const map = {};
    arr1.forEach(a => {
        map[a] = map[a] ? map[a] + 1 : 1;
    })
    const result = [];
    for(let key of arr2) {
        if(key in map && map[key] > 0) {
            result.push(key);
            map[key]--;
        }
    }
    return result;
};
console.log(intersect(arr1, arr2));

コードの解説

このコードで行っている処理の手順は以下のとおりです。

• まず最初の配列（arr1）をループし、各要素の出現回数をオブジェクト（map）に記録します。

• 続いて2つ目の配列（arr2）をループし、その要素が arr1 の出現回数マップに存在するかどうかを確認します。

• 存在する場合は、マップ上のカウントを1減らし、その要素を結果配列に追加します。これにより、重複した出現回数も正しく結果に反映されます。

計算量のポイント

このアルゴリズムでは、各配列をそれぞれ1回ずつ走査するだけで済むため、時間計算量は O(n + m)（n と m はそれぞれの配列の長さ）になります。要素の照合をハッシュマップで行うことで、二重ループによる O(n × m) の非効率なアプローチを避けている点が大きな特徴です。

出力

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

[7, 7, 4]