JavaScriptで配列内の同一要素をサブ配列にグループ化する方法

問題の概要

重複した要素を含む数値の配列が与えられたとき、その配列を受け取り、値が同じ要素どうしをひとつのサブ配列にまとめて、新しい配列として返す関数を作成するのが課題です。

たとえば、次のようになります。

// 入力配列が以下の場合：
const arr = [1, 3, 3, 1];
// 出力は次のようになります：
const output = [[1, 1], [3, 3]];

アプローチ：ハッシュマップで出現済みの要素を管理する

この問題を解くには、すでに出現した要素と、それが属するサブ配列のインデックスを記録しておくためのハッシュマップ（JavaScriptではオブジェクト）を使用します。そして、forループで配列を先頭から順に走査しながら、各要素を対応するグループへ追加していきます。

具体的な処理の流れは以下のとおりです。

• 初めて登場する要素であれば、新しいサブ配列を作成して group に追加し、そのインデックスをマップに記録します。
• すでに記録済みの要素であれば、マップに保存されたインデックスを参照して、該当するサブ配列に要素を追加します。

コード例

const arr = [1, 3, 3, 1];
const groupArray = arr => {
    const map = {};
    const group = [];
    for(let i = 0; i < arr.length; i++){
        if(typeof map[arr[i]] === 'number'){
            // すでに存在するグループに要素を追加
            group[map[arr[i]]].push(arr[i]);
        } else {
            // pushメソッドは追加後の配列の長さを返すため、
            // 新しく追加された要素のインデックスは「長さ - 1」となる
            map[arr[i]] = group.push([arr[i]]) - 1;
        }
    };
    return group;
}
console.log(groupArray(arr));

ポイント解説

このコードで重要なのは、group.push([arr[i]]) の戻り値の扱いです。JavaScriptの push() メソッドは、要素を追加した後の配列の新しい長さを返します。したがって、新しく作成されたサブ配列のインデックスは「長さ − 1」になります。この性質を利用することで、map オブジェクトに各値と対応するグループのインデックスを効率的に登録できます。

また、typeof map[arr[i]] === 'number' という条件式により、その要素がまだどのグループにも登録されていない場合（値が undefined のとき）と、すでにインデックスが記録されている場合とを正確に判定できます。

出力結果

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

[ [ 1, 1 ], [ 3, 3 ] ]

まとめ

ハッシュマップで「値 → グループのインデックス」という対応関係を管理すれば、配列を一度走査するだけで同一要素をサブ配列にまとめることができます。計算量は O(n) となるため、要素数が多い配列でも効率的に動作します。オブジェクトの代わりに Map を使えば、数値以外のキーでもより安全に扱えるので、状況に応じて使い分けるとよいでしょう。