Einfach 2 gelöst 66.7% Erfolgsquote

Fehlende Zahl

Finde die eine Zahl, die in 0..n fehlt.

Das lernst du

  • Die erwartete Summe von 0..n berechnen
  • Den fehlenden Wert aus der Differenz finden
  • Es in einem Durchlauf ohne Sortieren lösen

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

Beispiel 1
Eingabe:
numbers = [3, 0, 1]

Erwartete Ausgabe:
expected = 2
Eingabe:
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.

Beispiel 2
Eingabe:
numbers = [0]

Erwartete Ausgabe:
expected = 1
Eingabe:
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 HJhettory Jurash Python 784 ms - 4/5 Code ansehen
2 KKKaneki Ken Python 874 ms - 3/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 2 vollständige Lösungen unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.