O(n) 時間と O(1) 空間を持つ配列内の重複を見つけるにはどうすればよいですか?

O(n) 時間と O(1) 空間で重複を見つけるための効率的なアルゴリズム

このプログラミングの課題では、効率的なアルゴリズムを求めます。 0 から n-1 の範囲の整数の配列内の重複要素を識別し、繰り返し表示するアルゴリズム。この課題には、O(n) 時間の計算量内で動作し、一定のメモリ空間のみを消費するアルゴリズムが必要です。

この問題に対する効果的なアプローチの 1 つは、「配列変更」手法です。アルゴリズムは次のように機能します:

1. 最初のループ:

   • 配列内の各要素を反復するループを初期化します。 A[i].
   • 各 A[i] について、A[A[i]] かどうかを判断します。 A[i] と等しい。
   • そうでない場合は、A[i] を A[A[i]] と交換する。

2. 2 番目のループ:

   • 各 A[i] を反復するループをリセットします
   • i と等しくない A[i] については、A[i] を出力します。このステップでは、重複しない要素の A[A[i]] が i に等しい (つまり、正しい位置にある) ため、重複要素が特定されます。

このアルゴリズムは、各要素が最初のループで最大 1 回チェックおよび変更されるため、O(n) 時間で動作します。さらに、追加のデータ構造が使用されないため、O(1) スペースのみが使用されます。

たとえば、入力配列 {1, 2, 3, 1, 3, 0, 6} について考えてみましょう。アルゴリズムの実行後、配列は次のように変更されます:

[1, 2, 3, 1, 3, 0, 0]

次に、2 番目のループで重複した要素 1 と 3 が出力されます。

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