再帰を使ってJavaScriptの配列から連続する重複要素を削除する方法

本記事では、数値または文字列の配列を受け取り、余分なメモリ領域を使用せずに連続する重複要素をすべて削除する関数の実装方法を解説します。

問題の概要

例えば、次のような入力配列が与えられたとします。

const arr = [17, 17, 17, 12, 12, 354, 354, 1, 1, 1];

この場合、期待される出力は以下の通りです。

const output = [17, 12, 354, 1];

ポイントは、隣り合う要素が同じ値である場合のみ削除対象となることです。離れた位置にある同じ値(例えば先頭と末尾に同じ数値がある場合)は残ります。

再帰による実装

ここでは、ループの代わりに再帰呼び出しを使って処理を実装します。配列を先頭から順に走査し、現在の要素と次の要素が一致していれば splice() メソッドで該当要素をその場で削除していきます。

具体的なコードは以下の通りです。

const arr = [17, 17, 17, 12, 12, 354, 354, 1, 1, 1];
const comp = (arr, len = 0, deletable = false) => {
   if(len < arr.length){
      if(deletable){
         arr.splice(len, 1);
         len--;
      }
      return comp(arr, len+1, arr[len] === arr[len+1])
   };
   return;
};
comp(arr);
console.log(arr);

コードの仕組み

• len: 現在チェックしているインデックス位置を表します。
• deletable: 直前の比較で「隣接する2つの要素が同一」だった場合に true となり、現在の要素を削除すべきかどうかを示します。
• 要素を削除した後は len-- でインデックスを調整し、削除によってずれた位置を正しく扱えるようにしています。

この関数は新しい配列を作成せず、元の配列を直接書き換えるため、追加のメモリ領域をほとんど消費しません。

実行結果

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

[ 17, 12, 354, 1 ]

まとめ

このように、再帰と splice() を組み合わせることで、余分なメモリを使わずに配列内の連続する重複要素を効率的に削除できます。配列の要素数が非常に大きい場合は、再帰の深さによるスタックオーバーフローに注意し、必要に応じて反復処理への置き換えも検討するとよいでしょう。