【JavaScript】配列内で最初に重複する要素のインデックスを返す方法

問題概要

配列の中で、少なくとも2回以上出現する要素のうち、最初に現れたもののインデックスを返す関数を作成します。すべての要素が1回しか出現しない場合は、-1 を返します。

この問題の条件は、定数空間(余分なメモリを追加で使用しないこと)で実装する必要があるという点です。つまり、Set や Map のような追加データ構造を使わずに解く必要があります。

解決アプローチ

この問題は、for ループで配列を先頭から順に走査し、Array.prototype.lastIndexOf() メソッドで重複をチェックすることで解決できます。

lastIndexOf() は指定した要素が配列内で最後に現れるインデックスを返します。その結果が現在のインデックスと一致しなければ、同じ値が後方にも存在する(=重複している)ことを意味します。したがって、条件が最初に成立した時点のインデックスが「最初の重複要素」の位置となります。

サンプルコード

const firstDuplicate = arr => {
    for(let i = 0; i < arr.length; i++){
        if(arr.lastIndexOf(arr[i]) !== i){
            return i;
        };
    };
    return -1;
}
console.log(firstDuplicate([3, 5, 6, 8, 5, 3])); // 0
console.log(firstDuplicate([0, 1, 2, 3, 4, 4, 5])); // 4
console.log(firstDuplicate([0, 1, 1, 2, 3, 4, 4, 5])); // 1
console.log(firstDuplicate([0, 1, 2, 3, 4, 9, 5])); // -1

実行結果

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

0
4
1
-1

コードの解説

1つ目の例では、配列 [3, 5, 6, 8, 5, 3] の先頭要素「3」がインデックス5にも存在するため、lastIndexOf() の結果(5)と現在のインデックス(0)が一致せず、即座に 0 が返されます。

2つ目の例では、値「4」が初めて重複するのはインデックス4なので 4 が返り、3つ目の例では値「1」の重複がインデックス1で発生するため 1 が返ります。最後の例のように重複が一切存在しない場合は -1 が返されます。

計算量について

この実装は空間計算量こそ O(1) で定数空間の条件を満たしますが、ループ内で毎回 lastIndexOf() を呼び出すため、時間計算量は O(n²) になります。配列サイズが非常に大きい場合やパフォーマンスが重要なケースでは、Set を使った O(n) の実装も検討するとよいでしょう。