Move Zeroes

Q: Wie verschiebt man Nullen ans Ende, ohne die Reihenfolge der anderen Elemente zu ändern?

Führe am Anfang einen write -Index für die nächste freie Position und durchsuche das Array mit einem zweiten Index. Jeder Wert ungleich null, den du findest, wird an die write -Position getauscht, und write rückt um eine Position nach rechts. Die Werte werden in der Reihenfolge platziert, in der du sie findest, sodass sich ihre relative Reihenfolge nie ändert.

LeichtZwei Zeiger

+10

Du erhältst ein Array aus Ganzzahlen nums. Verschiebe jede 0 ans Ende des Arrays und behalte die Reihenfolge der anderen Werte bei. Gib das neu angeordnete Array zurück, das dieselbe Länge wie nums hat.

Funktion

moveZeroes(nums: integer-array) → integer-array

numsinteger-array: das Array der umzuordnenden Ganzzahlen
Gibt zurückinteger-array: nums mit den Werten ungleich 0 zuerst, in ihrer ursprünglichen Reihenfolge, und allen 0 am Ende

Einschränkungen

1 ≤ nums.length ≤ 5000
-10⁵ ≤ nums[i] ≤ 10⁵

Beispiele

Eingabe: nums = [0, 4, 0, 7, 2]
Ausgabe: [4, 7, 2, 0, 0]
Erklärung: Die Werte, die nicht 0 sind, sind 4, 7 und 2, und sie behalten diese Reihenfolge am Anfang bei. Die beiden 0en füllen die letzten beiden Plätze.

+14 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du stattdessen jede 0 an den Anfang verschieben und dabei die Reihenfolge der anderen Werte beibehalten, und das in einem Durchlauf mit O(1) zusätzlichem Speicher?

Tipps

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

0 von 3 geöffnet

Lösung

Die Nullen ans Ende zu verschieben, ist nicht der schwierige Teil. Die übrigen Werte in ihrer ursprünglichen Reihenfolge zu belassen, ist es – dadurch scheidet es aus, jede 0 mit dem letzten Element zu vertauschen. Teile das Array in einen vorderen Bereich auf, der die bisher gefundenen Werte ungleich null enthält, und den Rest. Ein Index liest jedes Element, ein zweiter markiert, wohin der nächste Wert ungleich null gehört, und ein einziger Durchlauf erledigt die Aufgabe direkt an Ort und Stelle.

Kopiere die Werte ungleich null

Idee

Erstelle ein neues Array. Gehe nums durch und kopiere jeden Wert, der nicht 0 ist, in der Reihenfolge, in der du ihn antriffst. Füge dann Nullen hinzu, bis das neue Array genauso lang ist wie nums. Die Anzahl der Nullen, die du hinzufügst, entspricht der Anzahl der übersprungenen Werte.

Bei [0, 4, 0, 7, 2] ergibt der Kopierschritt [4, 7, 2], und zwei Nullen machen daraus [4, 7, 2, 0, 0]. Die Reihenfolge stimmt, weil du die Werte in der Reihenfolge kopierst, in der du sie liest.

Jedes Element wird einmal gelesen und einmal geschrieben, also beträgt die Laufzeit O(n). Das zweite Array benötigt O(n) Speicher, den der nächste Ansatz vermeidet.

Algorithmus

Erstelle ein leeres Ergebnis-Array.
Füge jeden Wert aus nums zum Ergebnis hinzu, wenn er nicht 0 ist.
Füge Nullen hinzu, bis das Ergebnis genauso viele Einträge wie nums hat.
Gib das Ergebnis zurück.

def moveZeroes(nums):
    result = [x for x in nums if x != 0]
    result += [0] * (len(nums) - len(result))
    return result

Zwei Zeiger, direktes Vertauschen

Idee

Verwende zwei Indizes. read besucht jedes Element von links nach rechts. write markiert, an welcher Stelle der nächste Wert ungleich null hingehört. Nach jedem Schritt gelten zwei Tatsachen: Alles vor write sind die bisher gesehenen Werte ungleich null in ihrer ursprünglichen Reihenfolge, und alles von write bis read ist 0.

Wenn nums[read] nicht 0 ist, tausche es mit nums[write] und bewege write einen Schritt nach rechts. Der Wert, der bei read landet, ist eine 0 aus dem Nullbereich oder derselbe Wert, wenn die beiden Indizes gleich sind. Werte ungleich null überspringen nur Nullen, niemals einander, daher bleibt ihre Reihenfolge erhalten.

Bei [0, 4, 0, 7, 2]: Die 4 an Index 1 wird mit Index 0 getauscht, sodass [4, 0, 0, 7, 2] entsteht. Die 7 an Index 3 wird mit Index 1 getauscht, sodass [4, 7, 0, 0, 2] entsteht. Die 2 an Index 4 wird mit Index 2 getauscht, sodass [4, 7, 2, 0, 0] entsteht. Ein Durchlauf und kein zweites Array: O(n) Zeit und O(1) Speicher.

Algorithmus

Setze write auf 0.
Bewege read vom ersten Index zum letzten.
Falls nums[read] nicht 0 ist, vertausche nums[read] mit nums[write] und addiere dann 1 zu write.
Gib nums zurück.

def moveZeroes(nums):
    write = 0  # nums[:write] holds the non-zero values found so far, in order
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

Stolperfallen und Grenzfälle

Die üblichen Fehler bringen entweder die Reihenfolge der anderen Werte durcheinander oder überspringen Elemente.

Wenn jede 0 mit dem letzten Element vertauscht wird, werden die Nullen verschoben, aber der Rest wird durcheinandergebracht: [0, 4, 7] wird zu [7, 4, 0].
Wenn Nullen aus dem Array gelöscht werden, während ein Index darüber läuft, werden Elemente übersprungen. In [0, 0, 5] rutscht beim Löschen von Index 0 die zweite 0 auf Index 0, während die Schleife zu Index 1 weitergeht. Durch jedes Löschen wird außerdem der Rest des Arrays verschoben, wodurch die Schleife O(n²) benötigt.
Prüfe x != 0, nicht x > 0. Negative Werte sind keine Nullen: [-1, 0, -2] muss zu [-1, -2, 0] werden, aber mit x > 0 gibt die Kopiervariante [0, 0, 0] zurück.
Ein Array ohne Nullen oder mit ausschließlich Nullen muss unverändert zurückgegeben werden. Bei der Vertauschungsvariante bleiben read und write bis zur ersten 0 gleich, sodass diese Vertauschungen nichts ändern.
In Lua und R beginnen Arrays bei 1, daher beginnt auch write bei 1.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Move Zeroes?

O(n). Beide Ansätze lesen jedes Element einmal. Das Kopieren der Werte ungleich null in ein neues Array benötigt zusätzlichen Speicherplatz von O(n), während der Zwei-Zeiger-Tausch innerhalb des Arrays mit zusätzlichem Speicherplatz von O(1) auskommt.

Wie verschiebt man Nullen ans Ende, ohne die Reihenfolge der anderen Elemente zu ändern?

Führe am Anfang einen write-Index für die nächste freie Position und durchsuche das Array mit einem zweiten Index. Jeder Wert ungleich null, den du findest, wird an die write-Position getauscht, und write rückt um eine Position nach rechts. Die Werte werden in der Reihenfolge platziert, in der du sie findest, sodass sich ihre relative Reihenfolge nie ändert.

Kann man Move Zeroes mit weniger Schreibvorgängen lösen?

Ja. Anstatt zu vertauschen, kopiere jeden Wert ungleich null nach nums[write] und fülle nach dem Durchlauf alle Stellen von write bis zum Ende mit 0. So wird jede Position höchstens einmal beschrieben. Du kannst auch einen Tausch überspringen, wenn read gleich write ist, da der Wert sonst wieder an die Stelle gesetzt würde, an der er bereits steht.

Warum ist „Move Zeroes“ ein Problem mit zwei Zeigern?

Ein Zeiger liest jedes Element, und der andere markiert das Ende des fertigen vorderen Teils. Beide bewegen sich nur vorwärts, sodass sie zusammen einen einzigen Durchlauf bilden. Dasselbe Lese- und Schreibmuster entfernt Duplikate aus einem sortierten Array oder filtert jeden Wert direkt im Array heraus.

Python

def moveZeroes(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

nums = [0, 4, 0, 7, 2]

Erwartet

[4, 7, 2, 0, 0]