JavaScriptで配列内の最初の重複要素を検出する方法

配列内で少なくとも2回出現する最初の要素のインデックスを返す関数を作成します。すべての要素が一度しか出現しない場合は -1 を返します。また、追加のメモリを使用しない定数空間（O(1)）で実装する必要があります。

それでは、この問題の解決策を見ていきましょう。

アプローチ

ここでは、for ループで配列を先頭から順に走査し、Array.prototype.lastIndexOf() メソッドを使って各要素に重複があるかどうかを判定します。

lastIndexOf() は、指定した要素が配列内で最後に出現する位置を返します。現在のインデックス i と lastIndexOf() の結果が異なる場合、その要素は後ろにもう一度出現している、つまり重複していることがわかります。

コード例

実装コードは以下の通りです。

const arr1 = [0, 1, 1, 2, 3, 4, 4, 5];

const firstRedundant = arr => {
  for (let i = 0; i < arr.length; i++) {
    if (arr.lastIndexOf(arr[i]) !== i) {
      return i;
    }
  }
  return -1;
};

console.log(firstRedundant(arr1)); // 1

実行結果

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

1

処理の流れ

上記の例では、インデックス 0 の要素 0 は lastIndexOf(0) の結果が 0 となり一致するため、重複ではありません。次のインデックス 1 の要素 1 は、lastIndexOf(1) の結果が 2 となり現在のインデックスと一致しないため、重複していると判定され、1 が返されます。

注意点

この方法は追加のメモリを必要としないため空間計算量は O(1) ですが、各要素ごとに配列全体を走査するため、時間計算量は O(n²) になります。配列のサイズが非常に大きい場合はパフォーマンスへの影響に注意が必要です。