Giriş: bu numaralara kez herhangi bir sayı ortaya çıkar n-1, 0. element içeren n elemanlarının bir dizi Verilen

Amaç : O(n) bu numaraları yinelenen bulmak ve sadece sabit bellek alanı kullanarak.

Örneğin, n 7 ve dizi{1, 2, 3, 1, 3, 0, 6}, cevap 1 ve 3 olmalı olalım. Benzer sorular buraya baktım ama cevapları HashSet vb gibi bazı veri yapıları kullanılır.

Aynı için etkili bir algoritma?

Buna ek işaret biti gerektirmeyen: ile geldim

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

İlk döngü elemanı x mevcut en az bir kez, eğer o kayıtlar biri konumunda A[x] olacak, böylece dizi permutes.

O(n) görünebilir unutmayın ilk allık, ama iç içe bir döngü olmasına rağmen, hala O(N) zaman çalışır. Bir takas olursa i A[i] != i ve her takas en az bir öğe ayarlar doğru önce değildi nerede A[i] == i böyle bu böyle ise orada ortaya çıkar. Bu swapları toplam sayısı (ve böylece while döngü vücudun infaz sayısı) 10 ** en fazla olduğu anlamına gelir.

İkinci döngü baskılar değerleri x A[x] eşit değil x - bu yana ilk döngü garanti x var en az bir kez, dizisi, bir örneği olacak A[x] bu demektir ki, baskılar bu değerler x olan yok dizi.

(Ideone link so you can play with it)