Sort Colors
Du erhältst ein Array nums, in dem jeder Wert 0, 1 oder 2 ist. Stell dir vor, sie stehen für drei Farben, zum Beispiel Rot, Weiß und Blau. Ordne das Array so um, dass zuerst alle 0en, dann alle 1en und danach alle 2en kommen, und gib es zurück.
Löse die Aufgabe ohne eine Sortierfunktion aus einer Bibliothek. Es geht darum, dein Wissen über die Werte zu nutzen.
Funktion
- numsinteger-array
- die Farben, jeweils 0, 1 oder 2
- Gibt zurückinteger-array
- dieselben Werte, zuerst alle 0, dann alle 1 und schließlich 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 entspricht das Ergebnis genau dem: 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 2er folgen ihr.
- Eingabe
- nums = [1]
- Ausgabe
- [1]
- Erklärung
- Ein einzelner Wert ist bereits sortiert, daher kommt das Array unverändert zurück.
+17 versteckte Tests beim Einreichen
Weiterführende Frage
Was würdest du ändern, wenn es k Farben statt drei 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 funktioniert in zwei Durchläufen. Stell dir für einen Durchlauf drei Bereiche vor, die gleichzeitig wachsen: 0en am Anfang, 2en am Ende, 1en dazwischen.
Behalte drei Indizes:
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
Jede Sortierung ergibt die richtige Reihenfolge. Die eigentliche Frage ist also, welche Schritte dir die drei Werte ersparen. Da nur 0, 1 und 2 vorkommen können, kannst du sie zählen und das Array in zwei Durchläufen neu anordnen. Mit drei Zeigern, die markieren, wo die 0en enden und wo die 2en beginnen, kannst du sogar alle Werte in einem einzigen Durchlauf an die richtige Stelle setzen. Diese Ein-Durchlauf-Partitionierung ist der niederländische Nationalflaggen-Algorithmus.
Bubble-Sort von Hand
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Ein Sortieren mit einer Bibliothek würde in O(n log n) funktionieren, aber die Aufgabenregeln schließen das aus, weil ein Interviewer sehen möchte, was du mit der Tatsache anfängst, dass es nur drei Werte gibt. Die naheliegende Lösung ist dann ein Sortieralgorithmus, den du selbst schreibst, und der einfachste, den man korrekt implementieren kann, ist Bubble-Sort: Durchlaufe das Array und vertausche zwei benachbarte Elemente, wenn sie in der falschen Reihenfolge stehen.
Bei einem Durchlauf wird der größte gefundene Wert bis ganz ans Ende befördert, wie eine aufsteigende Blase. Nach dem ersten Durchlauf steht die letzte Position endgültig fest, nach dem zweiten die letzten beiden, also bringen n-1 Durchläufe das ganze Array in die richtige Reihenfolge. In [2, 1, 0] bewegt der erste Durchlauf die 2 ans Ende und ergibt [1, 0, 2]; beim zweiten Durchlauf werden die 1 und die 0 vertauscht.
Der Algorithmus ist langsam, weil bei jedem Durchlauf jedes Paar verglichen wird, dessen Position noch nicht endgültig feststeht: insgesamt etwa n²/2 Vergleiche. Bei n = 1.5 × 10^4 sind das über 10^8 Vergleiche, zuzüglich eines Tauschs für jedes Paar, das anfangs in der falschen Reihenfolge steht, und keine dieser Operationen nutzt die Tatsache, dass es nur drei verschiedene Werte gibt.
Algorithmus
- Führe n-1 Durchläufe über das Array aus.
- Vergleiche in jedem Durchlauf jedes noch nicht endgültige benachbarte Paar
nums[j]undnums[j + 1]und vertausche die beiden, wenn der linke Wert größer ist. - Nach dem Durchlauf Nummer
done(beginnend bei 0) enthalten die letztendone + 1Positionen ihre endgültigen Werte, daher endet der nächste Durchlauf vor ihnen. - 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 numsJede Farbe zählen und dann neu schreiben
Idee
Bubble Sort verbringt seine gesamte Zeit damit, benachbarte Elemente zu vergleichen, aber du weißt bereits, welche Werte vorkommen. Wenn das Array zwei 0en, drei 1en und zwei 2en enthält, steht die Antwort fest, bevor du irgendetwas verschiebst: zwei 0en, drei 1en, zwei 2en. Es kommt nur auf die Anzahlen an.
Lies also das Array einmal durch und zähle jeden Wert. Überschreibe es dann von Anfang an: count[0] Nullen, dann count[1] Einsen, dann count[2] Zweien. Das ist Counting Sort und hier sicher, weil gleiche Werte austauschbar sind. Eine 1 ist eine 1, also muss nichts von der ursprünglichen Reihenfolge erhalten bleiben.
Das sind zwei Durchläufe und drei Zähler, O(n) Zeit und O(1) Speicherplatz. Damit werden die Schranken eingehalten, und bei vielen Farben ist das die naheliegende Lösung. Die bekannte Anschlussfrage zu diesem Problem lautet, ob du es schaffst, während du das Array nur einmal durchliest.
Algorithmus
- Erstelle drei Zähler, alle auf 0.
- Lies jeden Wert und addiere eins zu seinem Zähler.
- Schreibe zuerst
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ändisches Flaggenproblem)
Idee
Während du das Array durchgehst, bilde drei Bereiche: 0en vorne, danach 1en, 2en hinten und einen noch ungelesenen Teil zwischen den 1en und den 2en. Drei Indizes markieren die Grenzen. Alles vor low ist 0, alles ab 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 gehört nach vorne: Tausche sie mit nums[low] und rücke sowohl low als auch mid weiter. Der Wert, der von low zurückkommt, ist eine 1 (oder dieselbe 0, wenn noch keine 1 gesehen wurde) und ist daher bereits an der richtigen Stelle. Eine 2 gehört nach hinten: Tausche sie mit nums[high] und rücke high zurück, aber lass mid an seiner Stelle, denn der Wert, der von high kommt, wurde noch nicht gelesen.
Bei jedem Schritt rückt mid vor oder high zurück, sodass der ungelesene Teil jedes Mal ein Element kleiner wird und die Schleife nach n Schritten endet. Verfolge [2, 0, 2]: Die erste 2 wird mit der letzten 2 getauscht und high sinkt auf 1; Index 0 enthält weiterhin eine 2, die mit der 0 getauscht wird, und high sinkt auf 0; Index 0 enthält nun die 0, die an ihrem Platz bleibt, und du erhältst [0, 2, 2].
Algorithmus
- Setze
low = 0,mid = 0undhighauf den letzten Index. - Lies
nums[mid], solangemid ≤ high. - Wenn der Wert 0 ist, tausche ihn mit
nums[low]und bewegelowundmidum einen Schritt nach rechts. - Wenn der Wert 1 ist, bewege
midum einen Schritt nach rechts. - Wenn der Wert 2 ist, tausche ihn mit
nums[high]und bewegehighum einen Schritt nach links. Lassemidan seiner Position. - 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
Die Ein-Pass-Version ist kurz, und fast jeder Fehler darin entsteht dadurch, dass sich ein Zeiger bewegt, obwohl er das nicht sollte.
midnach einem Tausch mithighweiterbewegen. Der ankommende Wert wurde noch nicht gelesen. 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, wennhighder Index des letzten ungelesenen Elements ist. Wenn die beiden zusammentreffen, ist dieses Element 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 2en enthält, wie[2], bringthighauf -1. In Rust, wo Indizesusizesind, solltehighstattdessen auf das Element direkt hinter dem ungelesenen Bereich zeigen, wie es der Rust-Code macht.- Davon ausgehen, dass jede Farbe vorkommt.
[2, 0, 2]enthält keine 1, und ein Array kann nur eine einzige Farbe enthalten. Die Zeigerregeln bewältigen beides ohne Sonderfälle, füge also keine hinzu.
Häufige Fragen4
Was ist das niederländische Flaggenproblem?
Edsger Dijkstra stellte folgende Aufgabe: Gegeben seien Objekte in drei Farben in einer Reihe, die Farben Rot, Weiß und Blau der niederländischen Flagge. Gruppiere jede Farbe in einem Durchgang zusammen und verwende dabei nur Vertauschungen. Sort Colors ist dasselbe Problem mit den Zahlen 0, 1 und 2. Seine Lösung ist die Partitionierung mit drei Zeigern low, mid und high.
Wie hoch sind die Zeit- und Speicherkomplexität von „Sort Colors“?
Die Lösung mit einem Durchlauf läuft in O(n) Zeit, 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 Grenzen, liest das Array aber zweimal.
Warum bewegt sich mid nach dem Tausch mit high nicht?
Der Wert, der von high zurückkommt, wurde noch nie gelesen, daher könnte er eine 0, eine 1 oder eine 2 sein. Würde man mid daran vorbeibewegen, bliebe eine 0 oder eine 2 in der Mitte. Ein Tausch mit low ist anders: Alles zwischen low und mid ist eine 1, daher ist der zurückkommende Wert bekannt und mid kann weitergehen.
Ist Counting Sort eine akzeptable Lösung für „Sort Colors“?
Es erfüllt die Zeitkomplexität O(n) und den Platzbedarf O(1), und viele Interviewer akzeptieren es als erste Antwort. Rechne mit der Anschlussfrage nach einem einzigen Durchlauf, bei der es um die Partitionierung mit drei Zeigern geht. 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.
Python
def sortColors(nums):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
nums = [2, 1, 0, 2, 0, 1, 1]
Erwartet
[0, 0, 1, 1, 1, 2, 2]