O(n) 時間、O(1) 空間で 0 から n-1 までの数値の配列内の重複をどのように見つけることができますか?

O(n) 時間と O(1) 空間での重複の検索

0 から n までの数値を含む n 要素の配列が与えられた場合-1、一部の数値が複数回出現する可能性がある場合、目標は、一定のメモリ空間を使用して O(n) 時間内に重複要素を見つけることです。

これを達成するには、次のような興味深いアプローチを利用できます。ハッシュ テーブルなどの追加のデータ構造は必要ありません。

提案されたアルゴリズムは次のように動作します:

1. 置換ループ:

   • 配列 for i を 0 から n-1 まで繰り返します。
   • このループ内で、A[A[i]] が A[i] と等しくなるまで次の手順を実行します。これは、要素 A[i] が正しい位置にあることを意味します。
   • A[i] を A[A[i]] と入れ替えます。これにより、要素 A[i] が正しい位置に効果的に一歩近づきます。

2. 重複識別ループ:

   • i を 0 から n-1 までもう一度繰り返します。
   • A[i] が i と等しくない場合、インデックス A[i] に i の重複があることを意味します。
   • A[i] を重複として印刷します。

このアルゴリズムにより、すべての重複要素が確実に識別されます。外側のループは n 回実行されますが、内側のループは最大でも n-1 回実行されます。したがって、アルゴリズムは O(n) 時間で実行されます。追加のデータ構造は使用しません。つまり、O(1) 空間で動作します。

提供されたコードは、C でのアルゴリズムの実装を例示しています。

以上がO(n) 時間、O(1) 空間で 0 から n-1 までの数値の配列内の重複をどのように見つけることができますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。