Sort Colors
Ti viene fornito un array nums in cui ogni valore è 0, 1 o 2: tre colori, come rosso, bianco e blu. Riordina l’array in modo che tutti gli 0 vengano prima, poi tutti gli 1 e infine tutti i 2, quindi restituiscilo. Risolvi il problema senza usare una funzione di ordinamento di una libreria.
Funzione
- numsinteger-array
- i colori, ciascuno 0, 1 o 2
- Restituisceinteger-array
- gli stessi valori con prima tutti gli 0, poi tutti gli 1 e infine tutti i 2
Vincoli
1 ≤ nums.length ≤ 1.5 × 104- Ogni
nums[i]è0,1o2. - Potrebbe mancare un colore e l'array potrebbe contenerne uno solo.
Esempi
- Input
- nums = [2, 1, 0, 2, 0, 1, 1]
- Output
- [0, 0, 1, 1, 1, 2, 2]
- Spiegazione
- L'array contiene due 0, tre 1 e due 2, quindi il risultato è esattamente questo: due 0, poi tre 1 e infine due 2.
- Input
- nums = [2, 0, 2]
- Output
- [0, 2, 2]
- Spiegazione
- Non c’è proprio nessun 1. L’unico 0 si sposta all’inizio e i due 2 lo seguono.
- Input
- nums = [1]
- Output
- [1]
- Spiegazione
- Un singolo valore è già ordinato, quindi l’array rimane invariato.
Per approfondire
Che cosa cambieresti se ci fossero k colori invece di tre, con k molto più piccolo della lunghezza dell’array?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Possono comparire solo tre valori diversi. Cosa ti permette di fare che un ordinamento generale non può?
Contare gli 0, gli 1 e i 2 e riscrivere l’array funziona in due passaggi. Per un passaggio, immagina tre regioni che crescono contemporaneamente: gli 0 davanti, i 2 dietro e gli 1 in mezzo.
Mantieni tre indici:
low,midehigh. Legginums[mid]: uno 0 viene scambiato conlow, un 2 conhigh, mentre un 1 resta dov’è. Dopo uno scambio conhigh, rileggi la stessa posizione.
Soluzione
Possono comparire solo 0, 1 e 2, quindi puoi contarli e riscrivere l’array in due passaggi. Tre puntatori che indicano dove finiscono gli 0 e dove iniziano i 2 lo fanno in un unico passaggio, mettendo ogni valore al suo posto mentre lo leggi. Questa partizione è l’algoritmo della bandiera nazionale olandese.
Ordinamento a bolle a mano
Corretto, ma non termina sui test più grandi
Intuizione
Senza un ordinamento fornito da una libreria, la soluzione di base è un ordinamento che scrivi tu. Il bubble sort scorre l’array e scambia due elementi adiacenti se sono nell’ordine sbagliato. A ogni passaggio porta il valore più grande incontrato fino alla fine, così dopo n-1 passaggi ogni posizione è definitiva.
Esegue circa n²/2 confronti: oltre 10^8 per n = 1.5 × 10^4, e nessuno di questi sfrutta il fatto che esistono solo tre valori.
Algoritmo
- Esegui n-1 passate sull'array.
- In ogni passata, confronta ogni coppia di elementi adiacenti
nums[j]enums[j + 1]che non è ancora definitiva, e scambiali quando quello a sinistra è più grande. - Dopo la passata numero
done(contando da 0), le ultimedone + 1posizioni contengono i loro valori definitivi, quindi la passata successiva si ferma prima di esse. - Restituisci
nums.
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 numsConta ogni colore, poi riscrivi
Intuizione
I valori uguali sono intercambiabili, quindi contano solo le quantità. Nel primo esempio, due 0, tre 1 e due 2 determinano la risposta prima ancora di spostare qualsiasi elemento.
Leggi l'array una volta per contare ogni valore, poi sovrascrivilo dall'inizio: count[0] zeri, count[1] uni, count[2] due. Questo è l'ordinamento per conteggio. Due passaggi e tre contatori richiedono tempo O(n) e spazio O(1).
Algoritmo
- Crea tre contatori, tutti a 0.
- Leggi ogni valore e aggiungi uno al relativo contatore.
- Scrivi
count[0]zeri dall'inizio, poicount[1]uni, poicount[2]due. - Restituisci
nums.
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 numsUn passaggio con tre puntatori (bandiera nazionale olandese)
Intuizione
Fai crescere tre regioni mentre leggi. Tutto ciò che precede low è 0, tutto ciò che va da low fino a, ma senza includere, mid è 1, tutto ciò che segue high è 2 e da nums[mid] a nums[high] è da leggere.
Leggi nums[mid]. Un 1 si trova già nella sua regione, quindi fai avanzare mid. Uno 0 viene scambiato con nums[low] ed entrambi avanzano: il valore che torna da low è un 1, oppure lo stesso 0 se non è ancora stato incontrato alcun 1, quindi è al suo posto. Un 2 viene scambiato con nums[high] e high arretra, ma mid resta fermo, perché il valore arrivato da high non è stato letto.
A ogni passaggio mid avanza o high arretra, quindi il ciclo termina dopo n passaggi. Con [2, 0, 2], il primo 2 viene scambiato con l’ultimo e high scende a 1; l’indice 0 contiene ancora un 2, che viene scambiato con lo 0; lo 0 resta quindi al suo posto e si ottiene [0, 2, 2].
Algoritmo
- Imposta
low = 0,mid = 0ehighall'ultimo indice. - Mentre
mid ≤ high, legginums[mid]. - Se è 0, scambialo con
nums[low]e spostalowemiddi un passo verso destra. - Se è 1, sposta
middi un passo verso destra. - Se è 2, scambialo con
nums[high]e spostahighdi un passo verso sinistra. Lasciamidal suo posto. - Restituisci
nums.
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
Trappole e casi limite
- Spostare
midin avanti dopo uno scambio conhigh. Il valore che arriva non è stato letto: in[1, 2, 0]il 2 viene scambiato con lo 0 e, saltando lo 0, si ottiene[1, 0, 2]. - Eseguire il ciclo mentre
mid < high. Quando i due si incontrano, quella cella non è ancora stata letta: in[1, 0]il ciclo si ferma prima di leggere lo 0 e restituisce[1, 0]. - Lasciare che
highscenda sotto zero con un indice senza segno. Un array contenente solo 2, come[2], portahigha -1, causando un underflow in unusizedi Rust. Mantieni invecehighun elemento oltre la parte non ancora letta.
Domande frequenti3
Che cos'è il problema della bandiera nazionale olandese?
Edsger Dijkstra l’ha formulato così: disponi in fila oggetti di tre colori, il rosso, il bianco e il blu della bandiera olandese, in modo che ogni colore sia raggruppato, con un solo passaggio e usando solo scambi. Sort Colors è lo stesso problema con 0, 1 e 2, e la sua soluzione è la partizione a tre puntatori.
Qual è la complessità temporale e spaziale di Sort Colors?
La soluzione in un solo passaggio richiede un tempo O(n), perché ogni passaggio riduce di una cella la parte non ancora letta. Usa uno spazio aggiuntivo O(1): tre indici e un valore temporaneo per lo scambio. L’ordinamento per conteggio ha gli stessi limiti, ma legge l’array due volte.
Il counting sort è una risposta accettabile per Sort Colors?
Rispetta i limiti di tempo O(n) e di spazio O(1), e molti intervistatori la accettano come prima risposta. Preparati a dover affrontare subito dopo una richiesta di soluzione in un'unica passata. Il conteggio è lo strumento migliore quando ci sono molti colori, poiché la partizione si divide soltanto in tre gruppi.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def sortColors(nums):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
nums = [2, 1, 0, 2, 0, 1, 1]
Output atteso
[0, 0, 1, 1, 1, 2, 2]