Sort Colors
Ti viene dato un array nums in cui ogni valore è 0, 1 o 2. Immagina che rappresentino tre colori, ad esempio rosso, bianco e blu. Riordina l'array in modo che tutti gli 0 vengano prima, poi tutti gli 1 e infine tutti i 2, e restituiscilo.
Risolvi il problema senza usare una funzione di ordinamento di una libreria. L'obiettivo è usare ciò che sai sui valori.
Funzione
- numsinteger-array
- i colori, ciascuno 0, 1 o 2
- Restituisceinteger-array
- gli stessi valori, prima tutti gli 0, poi tutti gli 1, quindi tutti i 2
Vincoli
1 ≤ nums.length ≤ 1.5 × 104- Ogni
nums[i]è0,1o2. - Potrebbe mancare un colore e l’array potrebbe contenere un solo colore.
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, poi due 2.
- Input
- nums = [2, 0, 2]
- Output
- [0, 2, 2]
- Spiegazione
- Non c'è alcun 1. Lo 0 singolo si sposta davanti e i due 2 lo seguono.
- Input
- nums = [1]
- Output
- [1]
- Spiegazione
- Un singolo valore è già in ordine, quindi l'array viene restituito senza modifiche.
+17 test nascosti all’invio
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ò fare?
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 all'inizio, i 2 alla fine e gli 1 in mezzo.
Mantieni tre indici:
low,midehigh. Legginums[mid]: uno 0 viene scambiato conlow, un 2 conhigh, un 1 resta al suo posto. Dopo uno scambio conhigh, leggi di nuovo la stessa posizione.
Soluzione
Qualsiasi ordinamento dà l'ordine giusto, quindi la vera domanda è cosa ti permettono di saltare i tre valori. Poiché possono comparire solo 0, 1 e 2, puoi contarli e riscrivere l'array in due passaggi. Con tre puntatori che indicano dove finiscono gli 0 e dove iniziano i 2, puoi persino mettere ogni valore al suo posto in un unico passaggio. Questa partizione in un solo passaggio è l'algoritmo della bandiera nazionale olandese.
Ordinamento a bolle a mano
Corretto, ma non termina sui test più grandi
Intuizione
Un ordinamento con una libreria avrebbe complessità O(n log n), ma il problema lo esclude, perché chi fa il colloquio vuole vedere cosa fai sapendo che ci sono solo tre valori. La soluzione di base è quindi un ordinamento che scrivi tu, e il più semplice da implementare correttamente è il bubble sort: scorri l’array e, ogni volta che due elementi adiacenti sono nell’ordine sbagliato, scambiali.
Una passata porta fino alla fine il valore più grande che incontra, come una bolla che sale. Dopo la prima passata l’ultima posizione è definitiva, dopo la seconda lo sono le ultime due, quindi n-1 passate mettono l’intero array in ordine. In [2, 1, 0] la prima passata sposta il 2 alla fine, ottenendo [1, 0, 2], e la seconda passata scambia l’1 e lo 0.
È lento perché ogni passata confronta ogni coppia che non è ancora nella posizione definitiva: in totale circa n²/2 confronti. Con n = 1.5 × 10^4 si superano 10^8 confronti, più uno scambio per ogni coppia inizialmente fuori ordine, e nessuna di queste operazioni 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 è maggiore. - Dopo la passata numero
done(contando da 0), le ultimedone + 1posizioni contengono i 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
Il bubble sort trascorre tutto il tempo a confrontare gli elementi vicini, ma sai già quali valori sono presenti. Se l’array contiene due 0, tre 1 e due 2, la risposta è definita prima ancora di spostare qualcosa: due 0, tre 1, due 2. Contano solo le quantità.
Quindi leggi l’array una volta e conta ogni valore. Poi sovrascrivilo dall’inizio: count[0] zeri, poi count[1] uni, poi count[2] due. Questo è il counting sort, ed è sicuro in questo caso perché i valori uguali sono intercambiabili. Un 1 è un 1, quindi non è necessario preservare nulla dell’ordine originale.
Si tratta di due passaggi e tre contatori, tempo O(n) e spazio O(1). Rispetta i limiti ed è la risposta naturale quando ci sono molti colori. La domanda successiva per cui questo problema è noto è se sia possibile farlo leggendo l’array una sola volta.
Algoritmo
- Crea tre contatori, tutti a 0.
- Leggi ogni valore e aggiungine 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: gli 0 all’inizio, gli 1 subito dopo, gli 2 alla fine e una parte non ancora letta tra gli 1 e gli 2. Tre indici segnano i confini. Tutto ciò che precede low è 0, tutto ciò che va da low fino a, ma non includendo, mid è 1, tutto ciò che segue high è 2 e da nums[mid] a nums[high] è ancora da leggere.
Leggi nums[mid]. Un 1 è già nella sua regione, quindi fai avanzare mid. Uno 0 va all’inizio: scambialo con nums[low] e fai avanzare sia low sia mid. Il valore che torna da low è un 1 (o lo stesso 0, se non è ancora stato trovato alcun 1), quindi è già al suo posto. Un 2 va alla fine: scambialo con nums[high] e fai arretrare high, ma lascia mid dov’è, perché il valore arrivato da high non è ancora stato letto.
A ogni passaggio mid avanza oppure high arretra, quindi la parte non ancora letta perde una cella ogni volta e il ciclo termina dopo n passaggi. Segui [2, 0, 2]: il primo 2 viene scambiato con l’ultimo 2 e high scende a 1; l’indice 0 contiene ancora un 2, che viene scambiato con lo 0 e high scende a 0; l’indice 0 ora contiene lo 0, che resta lì, e ottieni [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 a destra. - Se è 1, sposta
middi un passo a destra. - Se è 2, scambialo con
nums[high]e spostahighdi un passo a 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
La versione a passaggio unico è breve e quasi tutti i bug al suo interno sono causati da un puntatore che si sposta quando non dovrebbe.
- 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 restituisce[1, 0, 2]. - Eseguire il ciclo mentre
mid < highquandohighè l’ultimo indice non ancora letto. Quando i due si incontrano, quella cella non è ancora stata letta. In[1, 0], il ciclo si interrompe prima di leggere lo 0 e restituisce[1, 0]. - Lasciare che
highscenda sotto zero usando un indice senza segno. Un array composto solo da 2, come[2], portahigha -1. In Rust, dove gli indici sonousize, mantieni invecehighun’unità oltre la parte non ancora letta, come fa il codice Rust. - Supporre che siano presenti tutti i colori. In
[2, 0, 2]non c’è alcun 1 e un array può contenere un solo colore. Le regole dei puntatori gestiscono entrambi i casi senza eccezioni, quindi non aggiungerne.
Domande frequenti4
Che cos'è il problema della bandiera nazionale olandese?
Edsger Dijkstra pose il problema così: dati oggetti di tre colori disposti in fila, il rosso, il bianco e il blu della bandiera olandese, raggruppa ogni colore in un solo passaggio, usando solo scambi. Sort Colors è lo stesso problema con i numeri 0, 1 e 2. La sua soluzione è la partizione con tre puntatori low, mid e high.
Qual è la complessità temporale e spaziale di Sort Colors?
La soluzione a 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. Il counting sort ha gli stessi limiti, ma legge l'array due volte.
Perché mid non si sposta dopo lo scambio con high?
Il valore che torna da high non è mai stato letto, quindi potrebbe essere uno 0, un 1 o un 2. Spostare mid oltre quel valore lascerebbe uno 0 o un 2 al centro. Uno scambio con low è diverso: tutto ciò che si trova tra low e mid è un 1, quindi il valore che torna è noto e mid può proseguire.
Il counting sort è una risposta accettabile per Sort Colors?
Rispetta i limiti di tempo O(n) e spazio O(1), e molti intervistatori la accettano come prima risposta. Aspettati la domanda successiva su come eseguire un unico passaggio: la partizione a tre puntatori. Il conteggio è lo strumento migliore quando ci sono molti colori, poiché la partizione divide solo in tre gruppi.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def sortColors(nums):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
nums = [2, 1, 0, 2, 0, 1, 1]
Atteso
[0, 0, 1, 1, 1, 2, 2]