Problem
Die Liste enthält n verschiedene Zahlen aus 0, 1, …, n, sodass genau eine Zahl in diesem Bereich fehlt. Finde sie. (Tipp: Vergleiche die erwartete Gesamtsumme mit der tatsächlichen Summe.)
Implementiere missing_number(numbers).
Eingabe
numbers: n verschiedene Zahlen aus 0 bis n.
Ausgabe
Gib die fehlende Zahl zurück.
Einschränkungen
0 ≤ n ≤ 100.000
Beispiele
Eingabe:
numbers = [3, 0, 1]
Erwartete Ausgabe:
expected = 2Eingabe:
std::vector<long long> numbers = {3, 0, 1};
Erwartete Ausgabe:
long long expected = 2;Eingabe:
long[] numbers = new long[] {3, 0, 1};
Erwartete Ausgabe:
long expected = 2;Erläuterung
n = 3, also ist der Bereich 0–3; 2 fehlt.
Eingabe:
numbers = [0]
Erwartete Ausgabe:
expected = 1Eingabe:
std::vector<long long> numbers = {0};
Erwartete Ausgabe:
long long expected = 1;Eingabe:
long[] numbers = new long[] {0};
Erwartete Ausgabe:
long expected = 1;Erläuterung
n = 1 und der Bereich ist 0–1; 1 fehlt.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Die Zahlen sollten den vollständigen Bereich von 0 bis n abdecken, außer einer Lücke.
Hinweis 2
Vergleiche die Summe des vollständigen Bereichs mit der tatsächlichen Summe der Liste.
Hinweis 3
Achte auf den Fall, dass der fehlende Wert 0 oder n ist.
Erwartete Komplexität
Zeit O(n), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.