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 Argumente und Aufrufstapel als Zusatzspeicher?

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: Version mit Schwanzaufruf

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

Eine Dreieckszahl T(n) ist die Summe der n natürlichen Zahlen von 1 bis n. Sie kann als n(n+1)/2 dargestellt werden. Wenn man also weiß, dass von 1001 natürlichen Zahlen nur eine einzige doppelt vorkommt, kann man einfach alle gegebenen Zahlen addieren und T(1000) subtrahieren. Das Ergebnis wird dieses Duplikat enthalten.

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

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