Zor algoritma soru

Question

Olası Yinelenen:
Quickest way to find missing number in an array of numbers

Girdi: sıralanmamış dizi bir [1, .., n] aralığı 0 tamsayılar biri hariç tümünü içerir, .., n

Sorun, O (n) zamanındaki eksik tam sayıyı saptamaktır. A'nın her elemanı, ikili olarak temsil edilen 'dur ve kullanılabilir olan tek işlem, 'un A [i] jth biti değerini döndürdüğü ve sabit zaman aldığı işlev biti (i, j) 'dir.

Herhangi bir fikrin var mı? Bir çeşit böl ve yönet algoritmasının uygun olacağını düşünüyorum, ama tam olarak ne yapmam gerektiğini düşünemiyorum. Şimdiden teşekkürler!

Answer 1

O nn(n+1)/21 ve n arasındaki sayıların toplamıdır matematiksel bir mülk. Sen 10 için bu görebilirsiniz: sadece buna 0 ekliyoruz beri

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 
= (1+10) + (2+9) + (3+8) +(4+7) + (5+6) 
= 11 + 11 + 11 + 11 + 11 
= 55 

Yani, uzantısı, n aracılığıyla 0 gelen sayıların toplamıdır. Yani yaptığınız şey, tüm sayıları toplayıp sayım yapmaktır, sonra eksik olanı bulmak için bu formülü kullanır.

Yani, gibi bir şey: tek tek bit ayıklamak ve toplanmasıyla gerçek sayılar bunları açmak gerekecek böylece bit(i,j) ile numarası alınıyor

count = 0 
sum = 0 
foreach num in list: 
    sum = sum + num 
    count = count + 1 
missing = count * (count+1)/2 - sum 

zordur.

Answer 2

Bu, bir bit sorusu, çünkü bit yöntemini kullanmak her bir sayı için her bir biti çevirmenizi gerektireceğinden, otomatik olarak O (n * j) olacak, yani j n'yi temsil eden bitlerin sayısıdır.

Sanırım paxdiablo'nun var, sanırım bit yöntemini kullanmayan bir çözüme izin veriliyor.

Answer 3

XOR operatörünü eklentiden daha hızlı olarak kullanabilirsiniz. Her bir bitime erişebildiğiniz için burada bitümlü bir XOR yapıyor olacaksınız. Burada kullanılacak ilkesi (A XOR B XOR A) = B

, örneğin: (1 XOR 2 XOR 3) bir XOR (1 XOR 2) = 3

for i=0 to n 
{ 
Total=Total XOR i 
} 

foreach element in A 
{ 
Total=Total XOR element 
}