Tricky Algorithmus Frage

Question

Mögliche Duplizieren:
Quickest way to find missing number in an array of numbers

Input: unsortierten Array A [1, .., n], die 0 alle bis auf eine der ganzen Zahlen im Bereich enthält, ..

Das Problem besteht darin, die fehlende ganze Zahl in O (n) Zeit zu bestimmen. Jedes Element von A ist binär dargestellt, und die einzige verfügbare Operation ist das Funktionsbit (i, j), das den Wert des j-ten Bits von A [i] zurückgibt und konstante Zeit benötigt.

Irgendwelche Ideen? Ich denke, dass ein Algorithmus zum Teilen und Herrschen richtig wäre, aber ich kann mir nicht vorstellen, was genau ich tun sollte. Danke im Voraus!

Answer 1

Es ist eine mathematische Eigenschaft, dass die Summe der Zahlen zwischen 1 und n wo nn(n+1)/2 ist. Sie können dies für 10 sehen:

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 

Also, durch die Erweiterung, ist die Summe der Zahlen 0-n da Sie nur 0 bis es das Hinzufügen sind. Also, was Sie tun, ist, addieren Sie alle Zahlen und behalten Sie eine Zählung bei, dann verwenden Sie diese Formel, um die fehlende herauszufinden.

Also, so etwas wie:

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

die Zahl mit bit(i,j) bekommen ist schwierig, so dass Sie die Bits einzeln extrahieren müssen werden und sie in tatsächliche Zahlen zum Summieren.

Answer 2

Es ist eine Trick Frage dann, da die Verwendung der Bit-Methode würde nur erfordern, dass Sie jedes Bit für jede Zahl, was bedeutet, es würde automatisch zu O (n * j) wo j ist die Anzahl der Bits, die n darstellt.

Ich denke, Paxdiablo hat es, vorausgesetzt, Sie haben eine Lösung, die nicht die Bit-Methode verwendet.

Answer 3

Sie könnten XOR-Operator als schneller als Zugabe verwenden. Da Sie Zugriff auf jedes Bit haben, machen Sie hier ein bitweises XOR. Das Prinzip hier verwendet werden soll (A XOR B XOR A) = B

zB: (1 XOR 2 XOR 3) XOR (1 XOR 2) = 3

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

foreach element in A 
{ 
Total=Total XOR element 
}