最適な時間と空間の複雑さで配列内の重複を見つけるにはどうすればよいですか?

最適な時間と空間の計算量で重複を見つける

はじめに:
重複要素を検出するタスク配列はプログラミングにおいてよくある問題です。ハッシュ テーブルのような補助データ構造を使用するソリューションはシンプルさを提供しますが、スペース効率が損なわれます。この記事では、一定のスペース消費 O(1) を維持しながら、線形時間 O(n) で重複を識別する独創的なアルゴリズムを紹介します。

問題ステートメント:
配列が与えられた場合0 から n-1 までの n 個の要素のうち、一部の数値が複数回出現する場合は、配列内の重複要素を見つけます。

最適アルゴリズム:

// Iterate through the array
for i = 0 to n - 1:
    // Swap elements until A[A[i]] = A[i]
    while A[A[i]] != A[i]:
        swap(A[i], A[A[i]])
    end while

// Identify duplicates based on A[i] != i
for i = 0 to n - 1:
    if A[i] != i:
        print A[i]
    end if
end for

洞察:
このアルゴリズムは、配列内の各要素が理想的にはインデックスに存在する必要があるという事実を利用します。配列の要素を使用して順列を作成し、存在する要素が正しいインデックスにマップされるようにします。最初のループは配列を反復処理し、スワップを通じて各要素が意図したインデックスに到達することを保証します。

説明:
最初のループは、任意の要素 x について、次のように配列を並べ替えます。少なくとも 1 回出現すると、1 つのインスタンスはインデックス A[x] になります。各スワップでは、間違った要素に対応するエントリが修正され、スワップの総数が要素数 N-1 で制限されることが保証されます。

2 番目のループは、それぞれのインデックスを出力することで重複を識別します。

結論:
このアルゴリズムは、入力配列を巧みに利用することで、配列内の重複要素を効率的に識別します。自体。 O(n) 時間と O(1) 空間の複雑さにより、幅広い実用的なアプリケーションに適しています。

以上が最適な時間と空間の複雑さで配列内の重複を見つけるにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。