Wie finde ich ein doppeltes Element in einem Array gemischter aufeinanderfolgender Ganzzahlen?

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

Angenommen, Sie haben ein Array mit 1001 Ganzzahlen. Die Ganzzahlen sind in zufälliger Reihenfolge, aber Sie wissen, dass jede der Ganzzahlen zwischen 1 und 1000 (einschließlich) liegt. Außerdem wird jede Nummer nur einmal im Array angezeigt, mit Ausnahme einer Nummer, die zweimal vorkommt. 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 Zusatzspeicher verwendet haben, können Sie einen Algorithmus finden, der diesen nicht benötigt?

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

Addieren Sie sie einfach alle und subtrahieren Sie die Summe, die Sie erwarten würden, wenn nur 1001 Zahlen 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 zum Auffinden der doppelten Nummer ein Hack oder Trick ist. Meine offizielle Antwort lautet: "Ich suche nicht nach einer doppelten Nummer, sondern nach einem doppelten Muster in einem Array von Bitmengen. Und XOR ist definitiv besser als ADD geeignet, um Bitmengen zu manipulieren." :-)

Update: Nur zum Spaß, bevor ich ins Bett gehe, hier ist eine "einzeilige" alternative Lösung, die keinen zusätzlichen Speicherplatz benötigt (nicht einmal einen Schleifenzähler), jedes Array-Element nur einmal berührt, zerstörungsfrei 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 zur Kompilierungszeit tatsächlich die zweite Hälfte dieses Ausdrucks berechnet, sodass der "Algorithmus" in genau 1002 Operationen ausgeführt wird.

Und wenn die Array-Elementwerte auch zur Kompilierungszeit bekannt sind, optimiert der Compiler die gesamte Anweisung 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 greift dreimal auf jedes Array-Element 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.

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 gibt es hier einen destruktiven Algorithmus, der sicher für jedes N bis zu MAX_INT skaliert werden kann.

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

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

Ich werde die Übung, herauszufinden, warum dies für Sie funktioniert, mit einem einfachen Hinweis verlassen :-):

a ^ a = 0
0 ^ a = a

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

Dies kann unter Verwendung des XORBedieners erfolgen.

Nehmen wir an, wir haben ein Array von Größen 5: 4, 3, 1, 2, 2
Welche sind am Index:                        0, 1, 2, 3, 4

Führen Sie nun eines XORaller Elemente und aller Indizes aus. Wir bekommen 2, welches das doppelte Element ist. Dies geschieht, weil 0beim XORing keine Rolle spielt. Die verbleibenden n-1Indizes werden mit denselben n-1Elementen im Array gepaart, 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 es sich um eine Interviewfrage handelt, ist es am besten, mit der additionsbasierten Lösung zu beginnen, die Überlaufbegrenzung zu ermitteln und dann die XORbasierte Lösung anzugeben:)

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

Addiere alle Zahlen. Die endgültige Summe ist die 1 + 2 + ... + 1000 + doppelte Zahl.

Um die Lösung von Francis Penov zu paraphrasieren.

Das (übliche) Problem ist: Wenn ein Array von ganzen Zahlen beliebiger Länge vorliegt, die nur Elemente enthalten, die gerade mal wiederholt werden, mit Ausnahme eines Werts, der ungerade mal wiederholt wird, ermitteln Sie diesen Wert.

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, sodass Sie die Lösung anpassen müssen, um diese Eigenart zu kompensieren.

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

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

Da Sie jedoch zusätzlichen Speicherplatz für den Index benötigen, wird Ihnen wahrscheinlich vergeben, wenn Sie auch eine zusätzliche Ganzzahl verwenden ... Die Einschränkung liegt höchstwahrscheinlich darin, dass Sie daran gehindert werden sollen, ein Array zu verwenden.

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

Addiere alle Zahlen. Die Summe der ganzen Zahlen 1..1000 ist (1000 * 1001) / 2. Der Unterschied zu dem, was Sie erhalten, ist Ihre 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 Summe subtrahieren . Dies wird die wiederholte Nummer geben, weil sum(array) = sum(1, 1000) + repeated number.

Einzeilige Lö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. Antwort .

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 ... also ist die Summe von 1 ... 1000 500500. Der Algorithmus lautet also:

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

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

Kein zusätzlicher Speicherbedarf (außer Schleifenvariable).

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

Zählen Argumente und Callstacks als Hilfsspeicher?

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

Edit: Tail Call 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 Sie also wissen, dass unter 1001 natürlichen Zahlen eine und nur eine Zahl dupliziert wird, können Sie leicht alle gegebenen Zahlen summieren und T (1000) subtrahieren. Das Ergebnis enthält dieses Duplikat.

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

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

Ich unterstütze das Hinzufügen aller Elemente und das Subtrahieren der Summe aller Indizes, aber dies funktioniert nicht, wenn die Anzahl der Elemente sehr groß ist. Dh es wird einen ganzzahligen Überlauf verursachen! Daher habe ich diesen Algorithmus entwickelt, der die Wahrscheinlichkeit eines ganzzahligen Überlaufs in hohem Maße verringert.

   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 kann ich den Index, in dem das doppelte Element vorhanden ist, nicht herausfinden!

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

Verbesserung der Antwort von Fraci basierend auf der Eigenschaft, aufeinanderfolgende XOR-Werte zu verwenden:

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

Wo:

// 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 / Mathe 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:

Finden Sie die Summe und das Produkt von Zahlen von 1 - (to) N, sagen wir SUM, PROD.

Finden Sie die Summe und das Produkt der Zahlen von 1 - N - x - y (nehmen Sie an, dass x, y fehlen), sagen Sie 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.

In der Aux-Version setzen Sie zuerst alle Werte auf -1 und überprüfen beim Iterieren, ob Sie den Wert bereits in das Aux-Array eingefügt haben. Wenn nicht (Wert muss dann -1 sein), einfügen. Wenn Sie ein Duplikat haben, ist hier Ihre Lösung!

In der Version ohne Aux rufen Sie ein Element aus der Liste ab und prüfen, ob der Rest der Liste diesen Wert enthält. Wenn es enthält, haben Sie es hier gefunden.

private static int findDuplicated(int[] array) {
    if (array == null || array.length < 2) {
        System.out.println("invalid");
        return -1;
    }
    int[] checker = new int[array.length];
    Arrays.fill(checker, -1);
    for (int i = 0; i < array.length; i++) {
        int value = array[i];
        int checked = checker[value];
        if (checked == -1) {
            checker[value] = value;
        } else {
            return value;
        }
    }
    return -1;
}

private static int findDuplicatedWithoutAux(int[] array) {
    if (array == null || array.length < 2) {
        System.out.println("invalid");
        return -1;
    }
    for (int i = 0; i < array.length; i++) {
        int value = array[i];
        for (int j = i + 1; j < array.length; j++) {
            int toCompare = array[j];
            if (value == toCompare) {
                return array[i];
            }
        }
    }
    return -1;
}