Sort Colors
Du erhältst ein Array nums, in dem jeder Wert 0, 1 oder 2 ist: drei Farben, zum Beispiel Rot, Weiß und Blau. Ordne das Array so um, dass zuerst alle 0en, dann alle 1en und schließlich alle 2en kommen, und gib es zurück. Löse die Aufgabe ohne eine Sortierfunktion aus einer Bibliothek.
Funktion
- numsinteger-array
- die Farben, jeweils 0, 1 oder 2
- Gibt zurückinteger-array
- dieselben Werte, zuerst alle 0, dann alle 1 und anschließend alle 2
Einschränkungen
1 ≤ nums.length ≤ 1.5 × 104- Jedes
nums[i]ist0,1oder2. - Eine Farbe kann fehlen, und das Array kann eine einzelne Farbe enthalten.
Beispiele
- Eingabe
- nums = [2, 1, 0, 2, 0, 1, 1]
- Ausgabe
- [0, 0, 1, 1, 1, 2, 2]
- Erklärung
- Das Array enthält zwei 0en, drei 1en und zwei 2en, also ist das Ergebnis genau das: zwei 0en, dann drei 1en, dann zwei 2en.
- Eingabe
- nums = [2, 0, 2]
- Ausgabe
- [0, 2, 2]
- Erklärung
- Es gibt überhaupt keine 1. Die einzelne 0 rückt an den Anfang, und die beiden 2en folgen ihr.
- Eingabe
- nums = [1]
- Ausgabe
- [1]
- Erklärung
- Ein einzelner Wert ist bereits sortiert, daher wird das Array unverändert zurückgegeben.
Weiterführende Frage
Was würdest du ändern, wenn es statt drei k Farben gäbe und k viel kleiner als die Länge des Arrays wäre?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Es können nur drei verschiedene Werte vorkommen. Was kannst du damit tun, was mit einer allgemeinen Sortierung nicht möglich ist?
Das Zählen der 0en, 1en und 2en und das Umschreiben des Arrays erfolgt in zwei Durchläufen. Stell dir für einen Durchlauf drei Bereiche vor, die gleichzeitig wachsen: 0en vorne, 2en hinten und 1en dazwischen.
Behalte drei Indizes bei:
low,midundhigh. Liesnums[mid]: Bei einer 0 wird mitlowgetauscht, bei einer 2 mithigh, eine 1 bleibt. Lies nach einem Tausch mithighdieselbe Position erneut.
Lösung
Es können nur 0, 1 und 2 vorkommen, also kannst du sie zählen und das Array in zwei Durchgängen neu schreiben. Drei Zeiger, die markieren, wo die 0en enden und wo die 2en beginnen, erledigen das in einem Durchgang und platzieren jeden Wert an der richtigen Stelle, während du ihn liest. Diese Partitionierung ist der Algorithmus der niederländischen Nationalflagge.
Bubble Sort von Hand
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Ohne eine Sortierfunktion aus einer Bibliothek ist die naheliegende Lösung eine Sortierung, die du selbst schreibst. Bubble Sort durchläuft das Array und vertauscht jeweils zwei benachbarte Elemente, wenn sie nicht in der richtigen Reihenfolge sind. Bei jedem Durchlauf wandert der größte Wert, auf den es trifft, ans Ende, sodass nach n-1 Durchläufen jede Position endgültig feststeht.
Das ergibt etwa n²/2 Vergleiche: bei n = 1.5 × 10^4 mehr als 10^8, und keiner davon nutzt die Tatsache, dass es nur drei Werte gibt.
Algorithmus
- Führe n-1 Durchläufe über das Array aus.
- Vergleiche in jedem Durchlauf jedes benachbarte Paar
nums[j]undnums[j + 1], das noch nicht an seiner endgültigen Position ist, und vertausche die beiden, wenn das linke Element größer ist. - Nach Durchlauf Nummer
done(beginnend bei 0) enthalten die letztendone + 1Positionen ihre endgültigen Werte, sodass der nächste Durchlauf vor diesen Positionen endet. - Gib
numszurück.
def sortColors(nums):
n = len(nums)
for done in range(n - 1):
# One pass: the largest value left so far bubbles to index n-1-done.
for j in range(n - 1 - done):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return numsZähle jede Farbe und schreibe sie dann neu
Idee
Gleiche Werte sind austauschbar, daher zählen nur die Häufigkeiten. Im ersten Beispiel legen zwei 0en, drei 1en und zwei 2en die Antwort fest, bevor du irgendetwas verschiebst.
Durchlaufe das Array einmal, um jeden Wert zu zählen, und überschreibe es dann von Anfang an: count[0] Nullen, count[1] Einsen, count[2] Zweien. Das ist Counting Sort. Zwei Durchläufe und drei Zähler ergeben eine Laufzeit von O(n) und einen Speicherbedarf von O(1).
Algorithmus
- Erstelle drei Zähler, alle auf 0.
- Lies jeden Wert und addiere eins zu seinem Zähler.
- Schreibe vom Anfang an
count[0]Nullen, danncount[1]Einsen und anschließendcount[2]Zweien. - Gib
numszurück.
def sortColors(nums):
count = [0, 0, 0] # how many 0s, 1s and 2s
for x in nums:
count[x] += 1
i = 0
for color in range(3):
for _ in range(count[color]):
nums[i] = color
i += 1
return numsEin Durchlauf mit drei Zeigern (niederländische Nationalflagge)
Idee
Verschiebe beim Durchlaufen drei Bereiche. Alles vor low ist 0, alles von low bis, aber nicht einschließlich mid ist 1, alles nach high ist 2, und nums[mid] bis nums[high] ist noch ungelesen.
Lies nums[mid]. Eine 1 ist bereits in ihrem Bereich, also rücke mid weiter. Eine 0 wird mit nums[low] vertauscht und beide rücken weiter: Der Wert, der von low zurückkommt, ist eine 1 oder dieselbe 0, wenn noch keine 1 gesehen wurde, also ist er an der richtigen Stelle. Eine 2 wird mit nums[high] vertauscht und high rückt zurück, aber mid bleibt stehen, weil der Wert, der von high kommt, noch ungelesen ist.
Bei jedem Schritt rückt mid vor oder high zurück, sodass die Schleife nach n Schritten endet. Bei [2, 0, 2] wird die erste 2 mit der letzten vertauscht und high sinkt auf 1; an Index 0 steht weiterhin eine 2, die mit der 0 vertauscht wird; die 0 bleibt dann an ihrem Platz, sodass [0, 2, 2] entsteht.
Algorithmus
- Setze
low = 0,mid = 0undhighauf den letzten Index. - Solange
mid ≤ highgilt, liesnums[mid]. - Wenn es 0 ist, tausche es mit
nums[low]und bewegelowundmideinen Schritt nach rechts. - Wenn es 1 ist, bewege
mideinen Schritt nach rechts. - Wenn es 2 ist, tausche es mit
nums[high]und bewegehigheinen Schritt nach links. Lassemidan seiner Stelle. - Gib
numszurück.
def sortColors(nums):
# nums[:low] are 0s, nums[low:mid] are 1s, nums[high + 1:] are 2s.
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
# The value swapped in from high is unread, so mid stays.
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return nums
Stolperfallen und Grenzfälle
midnach einem Tausch mithighweiterbewegen. Der ankommende Wert ist noch ungelesen: Bei[1, 2, 0]wird die 2 mit der 0 getauscht, und wenn die 0 übersprungen wird, ergibt sich[1, 0, 2].- Die Schleife ausführen, solange
mid < highgilt. Wenn die beiden aufeinandertreffen, ist diese Zelle noch ungelesen: Bei[1, 0]endet die Schleife, bevor sie die 0 liest, und gibt[1, 0]zurück. highmit einem vorzeichenlosen Index unter null fallen lassen. Ein Array, das nur aus 2ern besteht, etwa[2], setzthighauf -1, was bei einem Rust-usizezu einem Unterlauf führt. Lasshighstattdessen auf die Position direkt hinter dem ungelesenen Teil zeigen.
Häufige Fragen3
Was ist das Problem der niederländischen Flagge?
Edsger Dijkstra stellte die Aufgabe: Ordne Objekte in drei Farben in einer Reihe an – Rot, Weiß und Blau, die Farben der niederländischen Flagge –, sodass jede Farbe gruppiert ist, und zwar in einem Durchgang und ausschließlich durch Vertauschen. Sort Colors ist dasselbe Problem mit 0, 1 und 2, und seine Lösung ist die Partitionierung mit drei Zeigern.
Wie hoch sind die Zeit- und Speicherkomplexität von „Sort Colors“?
Die Lösung mit einem Durchlauf hat eine Laufzeit von O(n), da jeder Schritt den ungelesenen Teil um eine Zelle verkleinert. Sie benötigt O(1) zusätzlichen Speicherplatz: drei Indizes und einen temporären Wert für den Tausch. Counting Sort hat dieselben Schranken, liest das Array jedoch zweimal.
Ist Counting Sort eine akzeptable Lösung für „Sort Colors“?
Es erfüllt die Grenzen von O(n) für die Laufzeit und O(1) für den Speicherbedarf, und viele Interviewer akzeptieren es als erste Antwort. Rechne damit, als Nächstes nach einem einzigen Durchlauf gefragt zu werden. Zählen ist das bessere Mittel, wenn es viele Farben gibt, da die Partitionierung nur in drei Gruppen aufteilt.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def sortColors(nums):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argument
nums = [2, 1, 0, 2, 0, 1, 1]
Erwartete Ausgabe
[0, 0, 1, 1, 1, 2, 2]