【JavaScript】線形時間とO(n)空間で配列内の重複要素を検出する方法

本記事では、1からnまでの範囲に含まれるn+1個の整数を持つ「読み取り専用」配列を引数として受け取るJavaScript関数の作成方法について解説します。

この関数が満たすべき要件は以下の2点です。

• 計算量が線形時間 O(n) であること
• 使用する追加メモリが最大でも O(n) であること

例えば、入力配列が次のような場合を考えてみましょう。

const arr = [3, 4, 1, 4, 1];

このとき、期待される出力の形式は以下の通りです。

const output = 1;

重複する数値が複数存在する場合(上記の例のように)、どれか1つを出力すれば問題ありません。また、重複が一切存在しない場合は -1 を返す仕様とします。

解決アプローチ:Setオブジェクトによる効率的な検出

最もシンプルかつ効果的な手法は、Set オブジェクトを活用することです。Setは要素の一意性を管理するのに適したデータ構造であり、要素の存在確認(has メソッド)や追加(add メソッド)を平均的に O(1) の計算量で実行できます。

アルゴリズムの手順は以下の通りです。

1. 空のSetを用意する。
2. 配列の各要素を先頭から順に走査する。
3. 現在の要素がすでにSetに存在していれば、それが重複要素であるため即座に返却する。
4. 存在しなければ、その要素をSetに追加する。
5. すべての要素を走査しても重複が見つからなければ、-1 を返す。

実装コード例

const arr = [3, 4, 1, 4, 1];
const findRepeatedNumber = (arr = []) => {
    const set = new Set();
    for (const item of arr) {
        if (set.has(item)){
            return item;
        };
        set.add(item);
    };
    return -1;
};
console.log(findRepeatedNumber(arr));

実行結果

上記のコードを実行すると、コンソールには次の出力が表示されます。

4

一見すると「1」が出力されそうに思えますが、実際には「4」が返されます。これは、配列を左から順に走査した際に、最初に2回目の出現が検出された要素が「4」だからです。つまり、この関数は「配列内で最初に繰り返し現れた時点の要素」を返すという点に注意してください。

パフォーマンス分析

このアプローチの計算量は以下の通りです。

• 時間計算量: O(n) — 配列の各要素を一度だけ走査し、Setへの操作は平均 O(1)
• 空間計算量: O(n) — 最悪の場合、ほぼすべての要素をSetに格納する必要がある

これにより、問題の制約である「線形時間・最大O(n)の空間使用量」という条件を満たしつつ、読み取り専用の配列に対しても安全に動作する実装となっています。