Wie finde ich ein doppeltes Element in einem Array von aufeinanderfolgenden aufeinanderfolgenden Ganzzahlen?

Ich bin kürzlich auf eine Frage gestoßen:

Angenommen, Sie haben ein Array von 1001 Ganzzahlen. Die ganzen Zahlen sind in zufälliger Reihenfolge, aber Sie wissen, dass jede der ganzen Zahlen zwischen 1 und 1000 (einschließlich) liegt. Außerdem erscheint jede Zahl nur einmal im Array, mit Ausnahme einer Nummer, die zweimal auftritt. Angenommen, Sie können nur einmal auf jedes Element des Arrays zugreifen. Beschreiben Sie einen Algorithmus, um die wiederholte Nummer zu finden. Wenn Sie in Ihrem Algorithmus Hilfsspeicher verwendet haben, können Sie einen Algorithmus finden, der dies nicht erfordert?

Was mich interessiert, ist der zweite Teil , dh ohne Zusatzspeicher . Hast du irgendeine Idee?

Fügen Sie sie alle hinzu und subtrahieren Sie die Summe, die Sie erwarten würden, wenn nur 1001 Nummern davon verwendet würden.

Z.B:

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

Update 2: Einige Leute denken, dass die Verwendung von XOR, um die doppelte Nummer zu finden, ein Hack oder Trick ist. Zu meiner offiziellen Antwort: “Ich bin nicht auf der Suche nach einer doppelten Nummer, ich suche nach einem Duplikatmuster in einem Array von Bit-Sets. Und XOR ist definitiv besser als ADD geeignet, um Bit-Sets zu manipulieren.” 🙂

Update: Nur zum Spaß, bevor ich ins Bett gehe, hier ist “One-Line” alternative Lösung, die Null zusätzlichen Speicherplatz (nicht einmal eine Schleife Zähler) benötigt, berührt jedes Array-Element nur einmal, ist nicht-destruktiv und skaliert überhaupt nicht: -)

 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 des Array-Elements zur Kompilierzeit bekannt sind, optimiert der Compiler die gesamte statement auf eine Konstante. 🙂

Ursprüngliche Lösung: Die nicht den strengen Anforderungen der Fragen entspricht, obwohl es funktioniert, um die richtige Antwort zu finden. Es verwendet eine zusätzliche Ganzzahl, um den Schleifenzähler beizubehalten, und es greift dreimal auf jedes Arrayelement zu – zweimal, um es zu lesen und es bei der aktuellen Iteration zu schreiben, und einmal, um es für die nächste Iteration zu lesen.

Nun, 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, ist hier ein destruktiver 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 Ihnen das gelingt, mit einem einfachen Hinweis :-):

 a ^ a = 0 0 ^ a = a 

Eine zerstörungsfreie Version der Lösung von Franci Penov.

Dies kann durch Verwendung des XOR Operators erfolgen.

Sagen wir, wir haben ein Array der Größe 5 : 4, 3, 1, 2, 2
Welche sind am Index: 0, 1, 2, 3, 4

Jetzt mache ein XOR von allen Elementen und allen Indizes. Wir erhalten 2 , das ist das doppelte Element. Dies geschieht, weil 0 beim XORing keine Rolle spielt. Die verbleibenden n-1 Indizes paaren mit den gleichen n-1 Elementen im Array und das einzige ungepaarte Element im Array ist das Duplikat.

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

Das beste Merkmal dieser Lösung ist, dass sie nicht unter Überlaufproblemen leidet, die in der additionsbasierten Lösung auftreten.

Da dies eine Interviewfrage ist, wäre es am besten, mit der additionsbasierten Lösung zu beginnen, die Überlaufbegrenzung zu identifizieren und dann die XOR basierte Lösung zu geben :)

Dies nutzt eine zusätzliche Variable und erfüllt damit die Anforderungen in der Frage nicht vollständig.

Füge alle Zahlen zusammen. Die endgültige Summe wird die 1 + 2 + … + 1000 + doppelte Nummer sein.

Um die Lösung von Francis Penov paraphrasieren.

Das (übliche) Problem ist: Wenn man ein Array von ganzen Zahlen beliebiger Länge vorgibt, die nur Elemente enthalten, die gerade mal wiederholt werden, außer einem Wert, der ungerade Male wiederholt wird, dann finde diesen Wert heraus.

Die Lösung ist:

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

Ihr aktuelles Problem ist eine Anpassung. Der Trick besteht darin, dass Sie das Element finden, das zweimal wiederholt wird, also müssen Sie die Lösung anpassen, um diese Eigenart zu kompensieren.

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

Was die Lösung von Francis am Ende macht, obwohl sie das ganze Array zerstört (nebenbei könnte es nur das erste oder letzte Element zerstören …)

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

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

Füge alle Zahlen hinzu. Die Summe der ganzen Zahlen 1..1000 ist (1000 * 1001) / 2. Der Unterschied zu dem, was du bekommst, ist deine Nummer.

Wenn Sie wissen, dass wir die genauen Zahlen 1-1000 haben, können Sie die Ergebnisse addieren und 500500 ( sum(1, 1000) ) von der sum(1, 1000) subtrahieren. Dies ergibt die wiederholte Zahl, weil sum(array) = sum(1, 1000) + repeated number .

Nun, es gibt eine sehr einfache Möglichkeit, dies zu tun … jede der Zahlen zwischen 1 und 1000 tritt genau einmal auf, außer für die Zahl, die wiederholt wird …. so ist die Summe von 1 …. 1000 500500. Also, der Algorithmus ist:

 Summe = 0
 für jedes Element des Arrays:
    sum + = das Element des Arrays
 number_that_occurred_twice = sum - 500500

Eine Linienlösung in Python

 arr = [1,3,2,4,2] print reduce(lambda acc, (i, x): acc ^ i ^ x, enumerate(arr), 0) # -> 2 

Erklärung, warum es funktioniert, ist in @Matthieu M.’s Antwort .

 n = 1000 s = sum(GivenList) r = str(n/2) duplicate = int( r + r ) - s 
 public static void main(String[] args) { int start = 1; int end = 10; int arr[] = {1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10}; System.out.println(findDuplicate(arr, start, end)); } static int findDuplicate(int arr[], int start, int end) { int sumAll = 0; for(int i = start; i < = end; i++) { sumAll += i; } System.out.println(sumAll); int sumArrElem = 0; for(int e : arr) { sumArrElem += e; } System.out.println(sumArrElem); return sumArrElem - sumAll; } 

Keine zusätzliche Speicheranforderung (außer Loop-Variable).

 int length = (sizeof array) / (sizeof array[0]); for(int i = 1; i < length; i++) { array[0] += array[i]; } printf( "Answer : %d\n", ( array[0] - (length * (length + 1)) / 2 ) ); 

Sind Argumente und Callstacks als Hilfsspeicher zu verstehen?

 int sumRemaining(int* remaining, int count) { if (!count) { return 0; } return remaining[0] + sumRemaining(remaining + 1, count - 1); } 
 printf("duplicate is %d", sumRemaining(array, 1001) - 500500); 

Bearbeiten: callbacke Version

 int sumRemaining(int* remaining, int count, int sumSoFar) { if (!count) { return sumSoFar; } return sumRemaining(remaining + 1, count - 1, sumSoFar + remaining[0]); } printf("duplicate is %d", sumRemaining(array, 1001, 0) - 500500); 
 public int duplicateNumber(int[] A) { int count = 0; for(int k = 0; k < A.Length; k++) count += A[k]; return count - (A.Length * (A.Length - 1) >> 1); } 

Eine Dreieckszahl T (n) ist die Summe der n natürlichen Zahlen von 1 bis n. Es kann als n (n + 1) / 2 dargestellt werden. Wenn man also weiß, dass unter 1001 natürlichen Zahlen eine und nur eine Zahl dupliziert ist, kann man einfach alle gegebenen Zahlen summieren und T (1000) subtrahieren. Das Ergebnis enthält dieses Duplikat.

Für eine Dreieckszahl T (n), wenn n eine Potenz von 10 ist, gibt es auch eine schöne Methode, dieses T (n) zu finden, basierend auf der Basis-10-Darstellung:

 n = 1000 s = sum(GivenList) r = str(n/2) duplicate = int( r + r ) - s 

Ich unterstütze die Addition aller Elemente und subtrahiere dann die Summe aller Indizes, aber dies funktioniert nicht, wenn die Anzahl der Elemente sehr groß ist. Dh es wird einen Integer-Überlauf verursachen! Also habe ich diesen Algorithmus entwickelt, der die Wahrscheinlichkeit eines ganzzahligen Überlaufs in einem großen Ausmaß reduzieren kann.

  for i=0 to n-1 begin: diff = a[i]-i; dup = dup + diff; end // where dup is the duplicate element.. 

Aber mit dieser Methode werde ich nicht in der Lage sein, den Index herauszufinden, bei dem das doppelte Element vorhanden ist!

Dafür muss ich das Array ein anderes Mal durchqueren, was nicht wünschenswert ist.

Verbesserung von Fracis Antwort basierend auf der Eigenschaft der XOR-Verknüpfung fortlaufender Werte:

 int result = xor_sum(N); for (i = 0; i < N+1; i++) { result = result ^ array[i]; } 

Woher:

 // Compute (((1 xor 2) xor 3) .. xor value) int xor_sum(int value) { int modulo = x % 4; if (modulo == 0) return value; else if (modulo == 1) return 1; else if (modulo == 2) return i + 1; else return 0; } 

Oder in Pseudocode / Math lang f (n) definiert als (optimiert):

 if n mod 4 = 0 then X = n if n mod 4 = 1 then X = 1 if n mod 4 = 2 then X = n+1 if n mod 4 = 3 then X = 0 

Und in kanonischer Form ist f (n):

 f(0) = 0 f(n) = f(n-1) xor n 

Meine Antwort auf Frage 2:

Finde die Summe und das Produkt der Zahlen von 1 – (bis) N, sagen SUM , PROD .

Finde die Summe und das Produkt der Zahlen von 1 – N-x -y, (nehme an, dass x, y fehlt), sage mySum, myProd,

So:

 SUM = mySum + x + y; PROD = myProd* x*y; 

So:

 x*y = PROD/myProd; x+y = SUM - mySum; 

Wir können x, y finden, wenn wir diese Gleichung lösen.