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

Alle Zahlen addieren. Die Summe der ganzen Zahlen 1..1000 ist (1000*1001)/2. Die Differenz zu dem, was du erhältst, ist deine Zahl.

Answer 2

Einzeilige Lösung in Python

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

Eine Erklärung, warum es funktioniert, finden Sie unter @Matthieu M.'s Antwort .

Answer 3

Nun, es gibt einen sehr einfachen Weg, dies zu tun... jede der Zahlen zwischen 1 und 1000 kommt genau einmal vor, mit Ausnahme der Zahl, die wiederholt wird...., so dass die Summe von 1....1000 500500 ist. Der Algorithmus lautet also:

sum = 0
for each element of the array:
   sum += that element of the array
number\_that\_occurred\_twice = sum - 500500

Answer 4

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

Answer 5

Kein zusätzlicher Speicherbedarf (abgesehen von der Schleifenvariablen).

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 )
);