Wie findet man ein doppeltes Element in einem Array aus gemischten, aufeinanderfolgenden ganzen Zahlen?

Question

Vor kurzem bin ich irgendwo auf eine Frage gestoßen:

Angenommen, Sie haben ein Array mit 1001 ganzen Zahlen. Die Zahlen sind in zufälliger Reihenfolge angeordnet, aber Sie wissen, dass jede der Zahlen zwischen 1 und 1000 (einschließlich) liegt. Außerdem kommt jede Zahl nur einmal in dem Array vor, mit Ausnahme einer Zahl, die zweimal vorkommt. Nehmen Sie an, dass Sie auf jedes Element des Arrays nur einmal zugreifen können. Beschreiben Sie einen Algorithmus, um die wiederholte Zahl zu finden. Wenn Sie in Ihrem Algorithmus Hilfsspeicher verwendet haben, können Sie einen Algorithmus finden, der diesen nicht benötigt?

Was mich interessiert, ist die zweiter Teil d.h., ohne Verwendung von Zusatzspeichern . Haben Sie eine Ahnung?

Answer 1

Zählen Sie einfach alle Zahlen zusammen und ziehen Sie davon die Summe ab, die Sie erwarten würden, wenn nur 1001 Zahlen verwendet würden.

Beispiel:

Input: 1,2,3,2,4 => 12
Expected: 1,2,3,4 => 10

Input - Expected => 2

Answer 2

Update 2: Manche Leute denken, dass die Verwendung von XOR zum Auffinden der doppelten Zahl ein Hack oder Trick ist. Meine offizielle Antwort darauf lautet: "Ich suche nicht nach einer doppelten Zahl, sondern nach einem doppelten Muster in einer Reihe von Bitmengen. Und XOR ist definitiv besser geeignet als ADD, um Bitsätze zu manipulieren" :-)

Aktualisierung: Nur zum Spaß, bevor ich ins Bett gehe, hier eine "einzeilige" Alternativlösung, die keinen zusätzlichen Speicherplatz benötigt (nicht einmal einen Schleifenzähler), jedes Array-Element nur einmal berührt, nicht destruktiv ist und überhaupt nicht skaliert :-)

printf("Answer : %d\n",
           array[0] ^
           array[1] ^
           array[2] ^
           // continue typing...
           array[999] ^
           array[1000] ^
           1 ^
           2 ^
           // continue typing...
           999^
           1000
      );

Beachten Sie, dass der Compiler die zweite Hälfte dieses Ausdrucks zur Kompilierzeit berechnet, so dass der "Algorithmus" in genau 1002 Operationen ausgeführt wird.

Und wenn die Werte der Array-Elemente auch zur Kompilierzeit bekannt sind, optimiert der Compiler die gesamte Anweisung auf eine Konstante :-)

Originelle Lösung: Das entspricht nicht den strengen Anforderungen der Fragen, auch wenn es funktioniert, um die richtige Antwort zu finden. Es verwendet eine zusätzliche Ganzzahl, um den Schleifenzähler zu halten, und es greift auf jedes Array-Element dreimal zu - zweimal, um es bei der aktuellen Iteration zu lesen und zu schreiben, und einmal, um es für die nächste Iteration zu lesen.

Sie benötigen mindestens eine zusätzliche Variable (oder ein CPU-Register), um den Index des aktuellen Elements zu speichern, während Sie das Array durchlaufen.

Abgesehen davon gibt es einen destruktiven Algorithmus, der sicher für jedes N bis zu MAX_INT skalieren kann.

for (int i = 1; i < 1001; i++)
{
   array[i] = array[i] ^ array[i-1] ^ i;
}

printf("Answer : %d\n", array[1000]);

Ich überlasse es Ihnen, herauszufinden, warum das funktioniert, und gebe Ihnen einen einfachen Tipp :-):

a ^ a = 0
0 ^ a = a

Answer 3

Eine nicht destruktive Version der Lösung von Franci Penov.

Dies kann durch die Verwendung der XOR Betreiber.

Nehmen wir an, wir haben ein Array der Größe 5 : 4, 3, 1, 2, 2
Die sich auf dem Index befinden:                        0, 1, 2, 3, 4

Machen Sie nun eine XOR aller Elemente und aller Indizes. Wir erhalten 2 was das doppelte Element ist. Dies geschieht, weil, 0 spielt bei der XOR-Verknüpfung keine Rolle. Die übrigen n-1 Indizes mit gleichem Paar n-1 Elemente im Array und die einziges ungepaartes Element im Array wird das Duplikat sein.

int i;
int dupe = 0;
for(i = 0; i < N; i++) {
    dupe = dupe ^ arr[i] ^ i;
}
// dupe has the duplicate.

Das Beste an dieser Lösung ist, dass sie nicht unter Überlaufproblemen leidet, wie sie bei der auf Addition basierenden Lösung auftreten.

Da es sich um eine Interviewfrage handelt, wäre es am besten, mit der additionsbasierten Lösung zu beginnen, die Überlaufbegrenzung zu ermitteln und dann die XOR basierte Lösung :)

Dabei wird eine zusätzliche Variable verwendet, so dass die Anforderungen der Frage nicht vollständig erfüllt werden.

Answer 4

Addiere alle Zahlen zusammen. Die Endsumme ist die Zahl 1+2+...+1000+Duplikat.

Answer 5

Um die Lösung von Francis Penov zu paraphrasieren.

Das (übliche) Problem lautet: Geben Sie eine Reihe ganzer Zahlen beliebiger Länge an, die nur Elemente enthalten, die gerade Male wiederholt werden, mit Ausnahme eines Wertes, der ungerade Male wiederholt wird. Finden Sie diesen Wert heraus.

Die Lösung ist:

acc = 0
for i in array: acc = acc ^ i

Ihr derzeitiges Problem ist eine Anpassung. Der Trick ist, dass Sie das Element finden sollen, das sich zweimal wiederholt, also müssen Sie die Lösung anpassen, um diese Eigenart auszugleichen.

acc = 0
for i in len(array): acc = acc ^ i ^ array[i]

Das ist es, was Francis' Lösung am Ende macht, obwohl sie das gesamte Array zerstört (übrigens könnte sie nur das erste oder letzte Element zerstören...)

Aber da Sie extra-Speicher für den Index benötigen, denke ich, dass Sie verziehen werden, wenn Sie auch eine zusätzliche Ganzzahl verwenden... Die Einschränkung ist höchstwahrscheinlich, weil sie verhindern wollen, dass Sie ein Array verwenden.

Es wäre genauer formuliert gewesen, wenn sie gefordert hätten O(1) Raum (1000 kann als N angesehen werden, da es hier willkürlich ist).