O(n) 時間、O(1) 空間で 0 から n-1 までの数値の配列内の重複を見つけるにはどうすればよいでしょうか?

O(n) 時間と O(1) 空間での重複の検索: 詳細な説明

提示された問題には、重複の特定が含まれます0 から n-1 までの範囲の数値を含む配列内の要素。課題は、O(n) 時間の計算量内で、一定 (O(1)) のメモリ空間のみを使用して、これを効率的に達成することにあります。

提示されたソリューションは、ハッシュ テーブルやその他の追加データを必要としない独創的な手法を採用しています。構造物。代わりに、配列自体の値を利用して重複要素を識別し、マークします。

1. 配列の並べ替え:

   内部ループは並べ替えます。次のロジックに基づく配列:

   while A[A[i]] != A[i]
       swap(A[i], A[A[i]])
   end while

   この置換ステップにより、要素 x が配列内に存在する場合、そのインスタンスの少なくとも 1 つが A[x] に配置されることが保証されます。これは後続のステップにとって非常に重要です。

2. 重複の識別:

   外側のループは各要素 A[i]:

   for i := 0 to n - 1
       if A[i] != i then
           print A[i]
       end if
   end for

   A[i] != i の場合、i が配列内の適切な場所に存在しないことを意味します。したがって、これは重複要素であり、出力されます。

3. 時間複雑性分析:

   この手法は O(n) 時間で実行されます。 。ネストされたループには、n 回反復する外側のループと、最大で n - 1 回の反復を実行する内側のループがあります (交換するたびに 1 つの要素が正しい位置に近づくため)。したがって、反復の総数は n*(n - 1) によって制限され、これは O(n^2) ですが、n*(n - 1) = n^2 - n として O(n) に単純化できます。 = n(n - 1) = n*n - n

4. 空間複雑性分析:

   アルゴリズムは定数空間のみを使用します、入力のサイズとは無関係です。重要な洞察は、置換に使用されるスペースが入力配列内にすでに存在しているということです。追加のストレージ構造は必要ありません。

5. 補足:

   アルゴリズムは、配列に 0 から n までの整数が含まれていることを前提としています。 1.
   • 重複が存在する場合でも、時間計算量は変わりません。
   • このアルゴリズムは、小規模から中程度のサイズの配列に対して効率的です。大規模な配列の場合は、ハッシュ テーブルなどのデータ構造を使用する代替アプローチの方が適している可能性があります。

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