Find the Duplicate Number

Q: Wie hoch ist die Zeitkomplexität von „Finde die doppelte Zahl“?

Floyds Zykluserkennung benötigt O(n) Zeit und O(1) zusätzlichen Speicher: Jede ihrer beiden Phasen folgt höchstens einer kleinen Zahl von Vielfachen von n Verknüpfungen. Die binäre Suche nach Werten benötigt O(n log n) Zeit und O(1) Speicher. Der Vergleich jedes Paars hat eine Laufzeit von O(n²) .

Q: Warum nicht eine Hash-Menge verwenden oder das Array sortieren?

Beide finden die Antwort in O(n) oder O(n log n) Zeit, und in einem echten Programm wären beide in Ordnung. Die Aufgabe verbietet sie absichtlich: Eine Hash-Menge benötigt O(n) zusätzlichen Speicher, und beim Sortieren wird entweder nums verändert oder eine vollständige Kopie benötigt. Diese Einschränkungen bringen dich dazu, den Zyklusansatz zu wählen.

Q: Warum funktioniert die Summenformel nicht für „Finde die doppelte Zahl“?

Wenn man 1 + 2 + ... + n von der Summe des Arrays abzieht, erhält man nur dann den doppelten Wert, wenn er genau zweimal vorkommt und jeder andere Wert einmal. Hier kann der wiederholte Wert viele Male vorkommen und fehlende Werte ersetzen. Bei [4, 2, 4, 1, 4] beträgt die Differenz 15 minus 10 = 5, was nicht einmal im Array vorkommt.

MittelSchneller und langsamer Zeiger Binäre Suche

+10

Du erhältst ein Array nums aus n+1 Ganzzahlen, von denen jede zwischen 1 und n liegt. Genau ein Wert kommt mehr als einmal vor, möglicherweise sehr oft, und du gibst diesen Wert zurück.

Löse die Aufgabe, ohne nums zu verändern und mit nur einer konstanten Menge an zusätzlichem Speicher.

Funktion

findDuplicate(nums: integer-array) → integer

numsinteger-array: n+1 ganze Zahlen, jeweils zwischen 1 und n
Gibt zurückinteger: der Wert, der mehr als einmal vorkommt

Einschränkungen

1 ≤ n ≤ 10⁴
nums.length == n+1
1 ≤ nums[i] ≤ n
Genau ein Wert kommt zwei- oder mehrmals vor; jeder andere Wert kommt höchstens einmal vor.

Beispiele

Eingabe: nums = [2, 5, 1, 3, 5, 4]
Ausgabe: 5
Erklärung: Hier ist n 5, und die 5 steht an den Positionen 1 und 4, also ist die Antwort 5. Jeder andere Wert von 1 bis 5 kommt einmal vor.

+17 versteckte Tests beim Einreichen

Weiterführende Frage

Die binäre Suche nach Werten hält beide Regeln in einer Zeit von O(n log n). Kannst du sie in einer Zeit von O(n) halten?

Tipps

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

0 von 3 geöffnet

Lösung

Eine Hash-Menge oder eine Sortierung findet das Duplikat sofort, aber beides verstößt gegen die Regeln: Die Menge benötigt Speicher für jeden Wert, und das Sortieren verändert nums. Die Lösung liegt in den Zahlen. Jeder Wert liegt zwischen 1 und n und ist daher auch eine gültige Position im Array. Lies jeden Wert als Verweis auf eine andere Position, und wenn du den Verweisen ab Position 0 folgst, landest du immer in einer Schleife, deren Einstieg das Duplikat ist. Floyds schnelle und langsame Zeiger finden diesen Einstieg mit zwei Ganzzahlen.

Vergleiche jedes Paar

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Der wiederholte Wert befindet sich mindestens an zwei Positionen i < j. Vergleiche jede Position mit jeder darauf folgenden Position; das erste Paar mit gleichen Werten liefert die Antwort. Im ersten Beispiel enthält Position 1 den Wert 5, und beim Durchsuchen ab Position 2 wird an Position 4 eine weitere 5 gefunden.

Damit bleiben beide Regeln erfüllt: Es wird nichts geschrieben, und der einzige Speicherbedarf besteht aus zwei Schleifenzählern. Das Verfahren ist langsam, weil es Paare vergleicht. Bei n+1 = 10,001 Werten und beiden Kopien nahe dem Ende prüft es etwa 5 × 10^7 Paare.

Algorithmus

Für jede Position i von 0 bis zum Ende:
Vergleiche für jede Position j nach i nums[i] mit nums[j].
Gib nums[i] beim ersten Treffer zurück.

def findDuplicate(nums):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                return nums[i]
    return -1  # unreachable: the input always holds a repeat

Binäre Suche nach dem Wert

Idee

Durchsuche den Wertebereich, nicht die Positionen. Wähle eine Grenze m und zähle, wie viele Einträge von nums höchstens m sind.

Wenn das Duplikat d größer als m ist, kommt jeder der Werte von 1 bis m höchstens einmal vor, also ist die Anzahl höchstens m. Wenn d höchstens m ist, kommt jeder Wert über m höchstens einmal vor, also sind höchstens n-m Einträge größer als m und mindestens m+1 höchstens m. Daher ist der Test „count > m“ für jedes m unterhalb von d falsch und ab d wahr. Die binäre Suche findet das erste m, für das der Test wahr wird, und das ist d.

Im zweiten Beispiel ist n gleich 4. Für m = 2 ergeben die Einträge 2 und 1 eine Anzahl von 2, also nicht mehr als 2; die Antwort ist daher größer als 2. Für m = 3 beträgt die Anzahl weiterhin 2, also ist die Antwort 4. Jeder Durchlauf liest das ganze Array einmal und halbiert den Bereich, daher beträgt der Aufwand O(n log n): etwa 14 Durchläufe über 10,001 Werte.

Algorithmus

Setze low = 1 und high = n, die Länge von nums minus eins.
Solange low < high gilt, nimm mid genau in der Mitte zwischen beiden.
Zähle die Einträge von nums, die höchstens mid sind.
Wenn die Anzahl größer als mid ist, setze high = mid; andernfalls setze low = mid+1.
Gib low zurück.

def findDuplicate(nums):
    low, high = 1, len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        # How many values fall in 1..mid?
        count = 0
        for x in nums:
            if x <= mid:
                count += 1
        if count > mid:
            high = mid      # 1..mid holds more values than it has room for
        else:
            low = mid + 1   # the repeat is above mid
    return low

Floyds Zykluserkennung in den Wertverknüpfungen

Idee

Lies das Array als Verknüpfungen: Position i zeigt auf Position nums[i]. Jede Position von 0 bis n hat genau eine ausgehende Verknüpfung, und jede Verknüpfung landet irgendwo zwischen 1 und n. Im ersten Beispiel lauten die Verknüpfungen 0 → 2, 1 → 5, 2 → 1, 3 → 3, 4 → 5 und 5 → 4.

Starte an Position 0 und folge den Verknüpfungen. Der Lauf kann niemals enden, weil jede Position eine Verknüpfung hat und es nur n+1 Positionen gibt; daher muss er zu einer bereits besuchten Position zurückkehren. Von da an dreht er endlos seine Runden. Der Pfad besteht aus einem Schwanzstück, gefolgt von einer Schleife, und hat die Form des griechischen Buchstabens ρ. Im ersten Beispiel verläuft der Lauf 0, 2, 1, 5, 4, 5, 4 und so weiter: Das Schwanzstück besteht aus 0, 2, 1 und die Schleife aus 5, 4. Position 3 zeigt auf sich selbst, aber der Lauf erreicht sie nie, und das ist kein Problem.

Der Eingang zur Schleife ist die doppelte Zahl. Der Lauf kommt aus verschiedenen Richtungen zweimal bei 5 an: einmal vom Ende des Schwanzstücks (Position 1, weil nums[1] 5 ist) und einmal vom Ende der Schleife (Position 4, weil nums[4] 5 ist). Zwei verschiedene Positionen enthalten den Wert 5, also kommt 5 doppelt vor. Das Schwanzstück enthält immer Position 0, weil kein Wert 0 ist und nichts zurück zu ihr zeigt; daher führen immer diese beiden unterschiedlichen Wege zum Eingang. Genau ein Wert kommt doppelt vor, also ist der Eingang dieser Wert.

Finde nun den Eingang mit zwei Zeigern, wie bei der Erkennung eines Zyklus in einer verketteten Liste. In Phase 1 folgt slow pro Runde einer Verknüpfung und fast zwei, bis beide an derselben Position irgendwo in der Schleife stehen. Im ersten Beispiel treffen sie sich bei 4. Setze in Phase 2 slow wieder auf 0, lasse fast an seiner Stelle und bewege beide pro Runde um eine Verknüpfung weiter. Sie treffen sich am Eingang.

Warum Phase 2 funktioniert: Angenommen, das Schwanzstück benötigt T Verknüpfungen bis zum Eingang und die Schleife umfasst C Positionen. Als sich die Zeiger trafen, hatte slow s Schritte zurückgelegt und fast 2s. Beide standen an derselben Stelle, also entsprachen die zusätzlichen s Schritte von fast ganzen Runden in der Schleife. Nach weiteren T Schritten erreicht slow von 0 aus den Eingang, und fast steht an der Stelle, an der ein Lauf von 0 aus nach s+T Schritten steht, da seine zusätzlichen Runden nichts ändern. Das sind T Schritte bis zum Eingang plus s Schritte, also eine ganze Anzahl von Runden; damit steht auch fast am Eingang. Sie können sich nicht früher treffen, weil slow noch auf dem Schwanzstück ist und fast die Schleife nie verlässt. Im ersten Beispiel geht slow die Positionen 2, 1, 5 entlang, während fast 5, 4, 5 durchläuft; nach T = 3 Schritten treffen sie sich bei 5.

Jede Phase benötigt O(n) Schritte, der einzige Speicherbedarf sind zwei Positionen, und nums wird nie verändert.

Algorithmus

Betrachte jede Position i als einen Knoten, der mit der Position nums[i] verknüpft ist, und setze beide Zeiger auf Position 0.
Phase 1: Bewege slow zu nums[slow] und fast zu nums[nums[fast]], bis sie gleich sind.
Phase 2: Setze slow wieder auf 0.
Bewege beide jeweils um eine Verknüpfung weiter, slow zu nums[slow] und fast zu nums[fast], bis sie gleich sind.
Gib diese Position zurück: Sie ist der wiederholte Wert.

def findDuplicate(nums):
    # Treat each index i as a node with one link, to nums[i].
    # Phase 1: slow moves one link, fast moves two, until they meet in the cycle.
    slow = fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    # Phase 2: restart one pointer at index 0 and move both one link at a time.
    # They meet at the cycle's entrance, the index two positions link to.
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

Stolperfallen und Grenzfälle

Die meisten falschen Antworten entstehen dadurch, dass Positionen und Werte verwechselt werden oder Floyds Methode eine Phase zu früh beendet wird.

Den Treffpunkt aus Phase 1 zurückgeben. Er ist irgendeine Position im Zyklus, nicht unbedingt der Eingang. Im ersten Beispiel treffen sich die Zeiger bei 4, aber die Antwort ist 5.
slow == fast vor dem ersten Schritt prüfen. Beide starten bei 0, also endet die Schleife sofort. Führe erst einen Schritt aus und vergleiche dann, oder starte sie ein beziehungsweise zwei Verbindungen weiter vorne.
Den Lauf an einer anderen Position als Position 0 beginnen. Keine Verbindung zeigt auf Position 0, da kein Wert 0 ist, und genau das garantiert einen Schwanz. An einer anderen Position zu beginnen, kann dich auf einen Zyklus ohne Zugang von außen bringen, wie etwa Position 3 im ersten Beispiel, dessen Eingang nichts beweist.
Annehmen, dass die Duplikate genau zweimal vorkommen. Der Summen-Trick, Gesamtwert minus 1 + 2 + ... + n, ergibt im zweiten Beispiel 15 minus 10 = 5, aber die Antwort ist 4. Dasselbe gilt für XOR-Tricks.
Eine binäre Suche über Positionen statt über Werte durchführen oder count >= mid prüfen. Die Anzahl der Werte kleiner oder gleich m ist genau m, wenn sich kein Wert von 1 bis m wiederholt und keiner fehlt. Deshalb trennt nur > die beiden Seiten.
Besuchte Werte markieren, indem nums[x] negiert oder Werte an ihre Stelle getauscht werden. Beides funktioniert, verändert aber das Array, was die Aufgabe verbietet.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von „Finde die doppelte Zahl“?

Floyds Zykluserkennung benötigt O(n) Zeit und O(1) zusätzlichen Speicher: Jede ihrer beiden Phasen folgt höchstens einer kleinen Zahl von Vielfachen von n Verknüpfungen. Die binäre Suche nach Werten benötigt O(n log n) Zeit und O(1) Speicher. Der Vergleich jedes Paars hat eine Laufzeit von O(n²).

Warum findet Floyds Zykluserkennung die doppelte Zahl?

Wenn du jeden Wert als Verweis von seiner Position auf die Position liest, die er benennt, muss der Weg ab Position 0 in einer Schleife enden, denn er hört nie auf und hat nur n+1 Positionen, die er durchlaufen kann. Die Position, an der er in die Schleife eintritt, wird von zwei verschiedenen Positionen aus erreicht, einer auf dem Schwanz und einer auf der Schleife, sodass zwei Einträge diesen Wert enthalten. Floyds Methode findet mit zwei Zeigern den Eintritt in eine Schleife und findet so den wiederholten Wert.

Warum nicht eine Hash-Menge verwenden oder das Array sortieren?

Beide finden die Antwort in O(n) oder O(n log n) Zeit, und in einem echten Programm wären beide in Ordnung. Die Aufgabe verbietet sie absichtlich: Eine Hash-Menge benötigt O(n) zusätzlichen Speicher, und beim Sortieren wird entweder nums verändert oder eine vollständige Kopie benötigt. Diese Einschränkungen bringen dich dazu, den Zyklusansatz zu wählen.

Warum funktioniert die Summenformel nicht für „Finde die doppelte Zahl“?

Wenn man 1 + 2 + ... + n von der Summe des Arrays abzieht, erhält man nur dann den doppelten Wert, wenn er genau zweimal vorkommt und jeder andere Wert einmal. Hier kann der wiederholte Wert viele Male vorkommen und fehlende Werte ersetzen. Bei [4, 2, 4, 1, 4] beträgt die Differenz 15 minus 10 = 5, was nicht einmal im Array vorkommt.

Python

def findDuplicate(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

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

Erwartet

Find the Duplicate Number

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Vergleiche jedes Paar

Binäre Suche nach dem Wert

Floyds Zykluserkennung in den Wertverknüpfungen

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben