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

同じ値のエントリが含まれる数値の配列があるとします。この配列を受け取り、同一の要素同士を1つのサブ配列にまとめた新しい配列を返す関数を作成する必要があります。

例

入力配列が次のような場合：

const arr = [234, 65, 65, 2, 2, 234];

期待される出力は以下のとおりです。同じ値がそれぞれ1つのサブ配列にまとめられています。

const output = [[234, 234], [65, 65], [2, 2]];

実装のアプローチ

この問題を解くには、ハッシュマップ（オブジェクト）を使って、すでに出現した要素と、その要素が格納されているサブ配列のインデックスを記録しておくのが効果的です。そのうえで、forループで配列を走査していきます。

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

• 各要素について、ハッシュマップにその値が登録済みかどうかを判定します。
• 登録済みの場合は、マップに記録されたインデックスを使って対応するサブ配列へ要素を追加します。
• 未登録の場合は、新しいサブ配列を作成してgroup配列に追加し、そのインデックスをハッシュマップに保存します。

コード例

実際のコードは次のようになります。

const arr = [234, 65, 65, 2, 2, 234];
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));

出力結果

このコードを実行すると、コンソールには次のように出力されます。

[ [ 234, 234 ], [ 65, 65 ], [ 2, 2 ] ]

処理のポイント

このアルゴリズムのポイントは、Array.prototype.push()の戻り値を活用している点です。pushメソッドは要素を追加した後の配列の新しい長さを返すため、そこから1を引けば、新しく作成したサブ配列のインデックスが求められます。これにより、追加の検索処理を行わずにハッシュマップへ効率的にインデックスを登録できます。

計算量としては、配列を一度だけ走査すればよいため、時間計算量はO(n)となり、大規模なデータに対しても高速に動作します。