Contains Duplicate

Q: Wie hoch ist die Zeitkomplexität von Contains Duplicate?

Die Lösung mit einem Hash-Set benötigt im Durchschnitt O(n) Zeit und O(n) zusätzlichen Speicherplatz. Zuerst zu sortieren benötigt O(n log n) Zeit und kein zusätzliches Array, wenn du die Eingabe umsortieren darfst. Jedes Paar zu vergleichen benötigt O(n²) Zeit.

Q: Kannst du „Enthält Duplikate“ ohne zusätzlichen Speicherplatz lösen?

Ja, wenn du das Array neu anordnen darfst: Sortiere es direkt und vergleiche jeden Wert mit seinem Nachbarn. Dadurch wird aus dem O(n) -Set eine Laufzeit von O(n log n) . Ohne Umordnung und ohne zusätzlichen Speicher bleibt nur der paarweise Vergleich mit O(n²) .

Q: Warum ist die Prüfung mit einer Hash-Menge schnell?

Ein Hash-Set speichert Werte anhand ihres Hashes. Daher lässt sich im Durchschnitt in konstanter Zeit statt durch Durchsuchen feststellen, ob es einen Wert enthält. Jedes Element erfordert eine Suche und ein Einfügen, wodurch der gesamte Durchlauf linear ist.

Q: Ist es eine gültige Lösung, die Größe der Menge mit der Länge des Arrays zu vergleichen?

Ja. Eine Menge aus allen Elementen von nums zu erstellen und zu prüfen, ob sie kleiner als das Array ist, liefert in O(n) -Zeit die richtige Antwort. Die Version mit der Schleife ist oft besser, weil sie zurückkehrt, sobald sie auf die erste Wiederholung trifft, während beim Erstellen der gesamten Menge immer jeder Wert gelesen wird.

LeichtHashing

+10

Du erhältst ein Array aus Ganzzahlen nums. Gib true zurück, wenn ein Wert darin mindestens zweimal vorkommt, und false, wenn alle Werte unterschiedlich sind.

Funktion

containsDuplicate(nums: integer-array) → boolean

numsinteger-array: die zu überprüfenden Ganzzahlen
Gibt zurückboolean: true, wenn ein Wert mindestens zweimal vorkommt, andernfalls false

Einschränkungen

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹

Beispiele

Eingabe: nums = [3, 1, 4, 1, 5]
Ausgabe: true
Erklärung: Der Wert 1 erscheint am Index 1 und erneut am Index 3, daher lautet die Antwort true.

Eingabe: nums = [2, 7, 1, 8]
Ausgabe: false
Erklärung: 2, 7, 1 und 8 sind vier verschiedene Werte, daher wiederholt sich nichts.

Eingabe: nums = [-4, 4, 0]
Ausgabe: false
Erklärung: -4 und 4 haben denselben Absolutwert, sind aber unterschiedliche Zahlen, und 0 kommt einmal vor, also lautet die Antwort false.

+17 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du aufhören, sobald du zum ersten Mal auf einen wiederholten Wert stößt, anstatt immer das ganze Array durchzugehen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Ein Wiederholungswert ist ein Wert, dem du bereits begegnet bist, und die Herausforderung besteht darin, schnell zu beantworten: „Bin ich diesem Wert schon begegnet?“ Ein Vergleich jedes Paars beantwortet die Frage, aber bei n = 10^4 sind das n(n-1)/2, also etwa 5 × 10^7 Vergleiche. Durch Sortieren werden gleiche Werte nebeneinander angeordnet, und ein Hash-Set beantwortet die Frage im Durchschnitt in O(1), sodass ein einziger Durchlauf genügt.

Sortieren und dann benachbarte Elemente vergleichen

Idee

In einem sortierten Array stehen gleiche Werte nebeneinander. [3, 1, 4, 1, 5] wird zu [1, 1, 3, 4, 5] sortiert, und die beiden 1er liegen nun nebeneinander. Nach dem Sortieren vergleichst du also nur noch jeden Wert mit dem direkt davor: n-1 Vergleiche statt der n(n-1)/2 Vergleiche, die nötig sind, um jedes Paar auszuprobieren.

Wenn keine zwei Nachbarn gleich sind, sind auch nirgendwo sonst zwei Werte gleich: Jeder Wert zwischen zwei Kopien von x in der sortierten Reihenfolge müsste mindestens x und höchstens x sein, also wäre er eine weitere Kopie von x.

Der Sortiervorgang bestimmt die Laufzeit von O(n log n). Wenn du nums direkt sortierst, brauchst du kein zusätzliches Array, aber die Eingabe des Aufrufers wird dabei umsortiert. Wenn das nicht zulässig ist, sortiere eine Kopie, was O(n) Speicherplatz kostet.

Algorithmus

Sortiere nums aufsteigend.
Durchlaufe i von 1 bis zum letzten Index.
Wenn nums[i] gleich nums[i-1] ist, gib true zurück.
Gib nach der Schleife false zurück.

def containsDuplicate(nums):
    nums.sort()
    # After sorting, equal values sit next to each other.
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return True
    return False

Ein Durchlauf mit einer Hash-Menge

Idee

Durchlaufe das Array einmal und speichere jeden Wert, an dem du bereits vorbeigekommen bist, in einer Hash-Menge. Bevor du einen Wert hinzufügst, prüfe, ob er bereits darin enthalten ist. Bei [3, 1, 4, 1, 5] wächst die Menge auf {3, 1, 4} an, und wenn die zweite 1 ankommt, ist sie bereits in der Menge enthalten, also gibst du true zurück, ohne die 5 zu lesen.

Die Menge enthält immer genau die Werte vor der aktuellen Position. Ein Treffer bedeutet also, dass der aktuelle Wert bereits früher aufgetreten ist. Erreichst du das Ende ohne Treffer, sind alle Werte verschieden.

Das Nachschlagen und Einfügen in eine Hash-Menge dauert im Durchschnitt O(1), daher ist der gesamte Durchlauf O(n). Der Preis dafür ist der Speicherbedarf: Gibt es keine Wiederholung, enthält die Menge am Ende alle n Werte.

Algorithmus

Erstelle eine leere Hash-Menge seen.
Wenn ein Wert in nums enthalten ist, gib true zurück, falls er in seen enthalten ist.
Andernfalls füge ihn zu seen hinzu.
Gib nach der Schleife false zurück.

def containsDuplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

Stolperfallen und Grenzfälle

Die Logik ist kurz, daher liegen die Fehler in den Schleifengrenzen und darin, was verglichen wird.

Jedes Paar vergleichen, wobei die innere Schleife bei j = i beginnt. Dann stimmt jeder Wert mit sich selbst überein und das Ergebnis ist immer true.
Nachbarn vergleichen, ohne vorher zu sortieren. In [9, 1, 2, 3, 9] stehen die beiden 9er nicht nebeneinander.
Die Nachbarschleife beim Index 0 beginnen und nums[-1] auslesen. Beginne bei 1; bei einem Array mit nur einem Wert wird korrekterweise false zurückgegeben.
Werte mit demselben Absolutwert als gleich behandeln, zum Beispiel durch Hashen von abs(x). -4 und 4 sind unterschiedliche Zahlen.
Einen C-Sortierkomparator schreiben, der x - y zurückgibt. Hier bleibt die Differenz innerhalb von ±2 × 10^9 und damit unter der int-Grenze von 2^31-1 = 2147483647, sodass sie zufällig noch hineinpasst; bei Werten nahe den int-Grenzen läuft sie über und die Sortierung ist falsch. Gib stattdessen (x > y) - (x < y) zurück.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Contains Duplicate?

Die Lösung mit einem Hash-Set benötigt im Durchschnitt O(n) Zeit und O(n) zusätzlichen Speicherplatz. Zuerst zu sortieren benötigt O(n log n) Zeit und kein zusätzliches Array, wenn du die Eingabe umsortieren darfst. Jedes Paar zu vergleichen benötigt O(n²) Zeit.

Kannst du „Enthält Duplikate“ ohne zusätzlichen Speicherplatz lösen?

Ja, wenn du das Array neu anordnen darfst: Sortiere es direkt und vergleiche jeden Wert mit seinem Nachbarn. Dadurch wird aus dem O(n)-Set eine Laufzeit von O(n log n). Ohne Umordnung und ohne zusätzlichen Speicher bleibt nur der paarweise Vergleich mit O(n²).

Warum ist die Prüfung mit einer Hash-Menge schnell?

Ein Hash-Set speichert Werte anhand ihres Hashes. Daher lässt sich im Durchschnitt in konstanter Zeit statt durch Durchsuchen feststellen, ob es einen Wert enthält. Jedes Element erfordert eine Suche und ein Einfügen, wodurch der gesamte Durchlauf linear ist.

Ist es eine gültige Lösung, die Größe der Menge mit der Länge des Arrays zu vergleichen?

Ja. Eine Menge aus allen Elementen von nums zu erstellen und zu prüfen, ob sie kleiner als das Array ist, liefert in O(n)-Zeit die richtige Antwort. Die Version mit der Schleife ist oft besser, weil sie zurückkehrt, sobald sie auf die erste Wiederholung trifft, während beim Erstellen der gesamten Menge immer jeder Wert gelesen wird.

Python

def containsDuplicate(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

nums = [3, 1, 4, 1, 5]

Erwartet

true