Sort Colors
Vous recevez un tableau nums dans lequel chaque valeur est 0, 1 ou 2 : trois couleurs, comme le rouge, le blanc et le bleu. Réorganisez le tableau pour que tous les 0 viennent d’abord, puis tous les 1, puis tous les 2, et retournez-le. Résolvez le problème sans utiliser de fonction de tri de bibliothèque.
Fonction
- numsinteger-array
- les couleurs, chacune valant 0, 1 ou 2
- Renvoieinteger-array
- les mêmes valeurs avec d’abord tous les 0, puis tous les 1, puis tous les 2
Contraintes
1 ≤ nums.length ≤ 1.5 × 104- Chaque
nums[i]vaut0,1ou2. - Une couleur peut être manquante, et le tableau peut contenir une seule couleur.
Exemples
- Entrée
- nums = [2, 1, 0, 2, 0, 1, 1]
- Sortie
- [0, 0, 1, 1, 1, 2, 2]
- Explication
- Le tableau contient deux 0, trois 1 et deux 2, le résultat est donc exactement cela : deux 0, puis trois 1, puis deux 2.
- Entrée
- nums = [2, 0, 2]
- Sortie
- [0, 2, 2]
- Explication
- Il n’y a aucun 1. Le seul 0 se déplace au début et les deux 2 le suivent.
- Entrée
- nums = [1]
- Sortie
- [1]
- Explication
- Une valeur unique est déjà en ordre, donc le tableau revient inchangé.
Pour aller plus loin
Que changerais-tu s’il y avait k couleurs au lieu de trois, avec k beaucoup plus petit que la longueur du tableau ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Seules trois valeurs différentes peuvent apparaître. Que peux-tu faire grâce à cela qu’un tri général ne permet pas ?
Compter les 0, les 1 et les 2 et réécrire le tableau se fait en deux passes. Pour une passe, imagine trois régions qui s’agrandissent en même temps : les 0 à l’avant, les 2 à l’arrière et les 1 entre les deux.
Gardez trois indices :
low,midethigh. Liseznums[mid]: un 0 est échangé avec l’élément àlow, un 2 avec celui àhigh, et un 1 reste en place. Après un échange avechigh, relisez la même position.
Solution
Seuls 0, 1 et 2 peuvent apparaître, donc tu peux les compter et réécrire le tableau en deux passes. Trois pointeurs indiquant où se terminent les 0 et où commencent les 2 permettent de le faire en une seule passe, en plaçant chaque valeur à sa place au fur et à mesure de la lecture. Cette partition est l’algorithme du drapeau national néerlandais.
Trier à bulles à la main
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Sans fonction de tri de bibliothèque, la référence est un tri que tu écris toi-même. Le tri à bulles parcourt le tableau et échange deux éléments voisins lorsqu’ils sont dans le désordre. À chaque passage, il déplace la plus grande valeur rencontrée jusqu’à la fin ; ainsi, après n-1 passages, toutes les positions sont définitives.
Il effectue environ n²/2 comparaisons : plus de 10^8 pour n = 1.5 × 10^4, sans jamais tirer parti du fait qu’il n’existe que trois valeurs.
Algorithme
- Effectuez n-1 passes sur le tableau.
- À chaque passe, comparez chaque paire de voisins
nums[j]etnums[j + 1]qui n’est pas encore définitive, et échangez-les lorsque celui de gauche est plus grand. - Après la passe numéro
done(en comptant à partir de 0), lesdone + 1dernières positions contiennent leurs valeurs définitives, donc la passe suivante s’arrête avant elles. - Retournez
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 numsCompte chaque couleur, puis réécris
Intuition
Les valeurs égales sont interchangeables, donc seuls les décomptes comptent. Dans le premier exemple, deux 0, trois 1 et deux 2 déterminent la réponse avant même que tu ne déplaces quoi que ce soit.
Parcours le tableau une fois pour compter chaque valeur, puis réécris-le à partir du début : count[0] zéros, count[1] uns, count[2] deux. C’est le tri par comptage. Deux parcours et trois compteurs donnent un temps O(n) et un espace O(1).
Algorithme
- Créez trois compteurs, tous à 0.
- Lisez chaque valeur et ajoutez-en une à son compteur.
- Écrivez
count[0]zéros au début, puiscount[1]uns, puiscount[2]deux. - Retournez
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 seul passage avec trois pointeurs (drapeau national néerlandais)
Intuition
Fais grandir trois régions pendant que tu lis. Tout ce qui précède low est égal à 0, tout ce qui va de low jusqu’à mid exclu est égal à 1, tout ce qui suit high est égal à 2, et la portion de nums[mid] à nums[high] n’a pas encore été lue.
Lis nums[mid]. Un 1 se trouve déjà dans sa région, alors avance mid. Un 0 est échangé avec nums[low] et les deux indices avancent : la valeur qui revient de low est un 1, ou le même 0 si aucun 1 n’a encore été rencontré, elle est donc à sa place. Un 2 est échangé avec nums[high] et high recule, mais mid reste sur place, car la valeur qui vient de high n’a pas encore été lue.
À chaque étape, mid avance ou high recule, donc la boucle se termine après n étapes. Avec [2, 0, 2], le premier 2 est échangé avec le dernier et high passe à 1 ; l’indice 0 contient toujours un 2, qui est échangé avec le 0 ; le 0 reste ensuite à sa place, ce qui donne [0, 2, 2].
Algorithme
- Définissez
low = 0,mid = 0ethighsur le dernier indice. - Tant que
mid ≤ high, liseznums[mid]. - S’il vaut 0, échangez-le avec
nums[low]et déplacezlowetmidd’un pas vers la droite. - S’il vaut 1, déplacez
midd’un pas vers la droite. - S’il vaut 2, échangez-le avec
nums[high]et déplacezhighd’un pas vers la gauche. Laissezmiden place. - Renvoyez
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
Pièges et cas limites
- Déplacer
midvers l’avant après un échange avechigh. La valeur qui arrive n’a pas été lue : dans[1, 2, 0], le 2 est échangé avec le 0, et ignorer le 0 renvoie[1, 0, 2]. - Boucler tant que
mid < high. Lorsque les deux se rejoignent, cette case n’a toujours pas été lue : dans[1, 0], la boucle s’arrête avant de lire le 0 et renvoie[1, 0]. - Laisser
highpasser sous zéro avec un indice non signé. Un tableau contenant uniquement des 2, comme[2], fait passerhighà -1, ce qui provoque un dépassement inférieur pour unusizeRust. Gardez plutôthighà une position après la partie non lue.
Questions fréquentes3
Qu’est-ce que le problème du drapeau national néerlandais ?
Edsger Dijkstra a posé le problème ainsi : disposer des objets de trois couleurs en rangée, le rouge, le blanc et le bleu du drapeau néerlandais, de sorte que chaque couleur soit regroupée, en un seul passage et en utilisant uniquement des échanges. Sort Colors est le même problème avec 0, 1 et 2, et sa solution est le partitionnement à trois pointeurs.
Quelle est la complexité temporelle et spatiale de Sort Colors ?
La solution en un seul parcours s’exécute en O(n), car chaque étape réduit la partie non lue d’une cellule. Elle utilise O(1) d’espace supplémentaire : trois indices et une valeur temporaire pour l’échange. Le tri par comptage a les mêmes bornes, mais parcourt le tableau deux fois.
Le tri par comptage est-il une réponse acceptable pour Sort Colors ?
Elle respecte les bornes de temps O(n) et d’espace O(1), et de nombreux recruteurs l’acceptent comme première réponse. Attends-toi ensuite à ce qu’on te demande de le faire en un seul parcours. Le comptage est un meilleur outil lorsqu’il y a beaucoup de couleurs, puisque le partitionnement ne sépare qu’en trois groupes.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def sortColors(nums):
# Écrivez le code iciTest #1
Test #2
Test #3
Argument
nums = [2, 1, 0, 2, 0, 1, 1]
Résultat attendu
[0, 0, 1, 1, 1, 2, 2]