☰

O(n) の時間と O(1) のスペースで重複を見つける 質問する

tag-icon • tag-icon c++ c algorithm
O(n) の時間と O(1) のスペースで重複を見つける 質問する

入力: 0 から n-1 までの要素が含まれ、これらの数字が任意の回数出現する n 要素の配列が与えられます。

目標: 定数のメモリ空間のみを使用して、O(n) でこれらの繰り返し番号を見つけます。

たとえば、n が 7 で配列が {1、2、3、1、3、0、6} の場合、答えは 1 と 3 になります。ここで同様の質問を確認しましたが、回答では次のようなデータ構造が使用されていましたHashSet。

同様の効率的なアルゴリズムはありますか?

ベストアンサー1

これは私が思いついたもので、追加の符号ビットを必要としません。

for i := 0 to n - 1
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

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

最初のループは配列を並べ替え、要素がx少なくとも 1 回存在する場合は、それらのエントリの 1 つが位置に配置されますA[x]。

一見すると O(n) に見えないかもしれませんが、実際は O(n) です。ネストされたループがありますが、それでも時間内に実行されます。swap はとなる がO(N)存在する場合にのみ発生し、各 swap は となる要素を少なくとも 1 つ設定します(以前はそうではありませんでした)。つまり、swap の合計数 (つまり、ループ本体の実行合計数) は最大 です。iA[i] != iA[i] == iwhileN-1

x2 番目のループは、 がA[x]等しくないの値を出力します。最初のループは、 が配列内に少なくとも 1 回存在するx場合、それらのインスタンスの 1 つが にあることを保証しているため、これは、配列内に存在しない の値を出力していることを意味します。xA[x]x

(Ideone のリンクがあるので、ぜひ試してみてください)

おすすめ記事