Sort Colors

Q: Qu’est-ce que le problème du drapeau national néerlandais ?

Edsger Dijkstra l’a posé ainsi : étant donné des objets de trois couleurs disposés en ligne, le rouge, le blanc et le bleu du drapeau néerlandais, regroupez chaque couleur en un seul passage, en utilisant uniquement des échanges. Sort Colors est le même problème avec les nombres 0, 1 et 2. Sa solution est le partitionnement à trois pointeurs avec low , mid et high .

Q: Quelle est la complexité temporelle et spatiale de Sort Colors ?

La solution en un seul passage s’exécute en temps O(n), car chaque étape réduit d’une case la partie non lue. Elle utilise un espace supplémentaire O(1) : trois indices et une valeur temporaire pour l’échange. Le tri par comptage a les mêmes bornes, mais parcourt le tableau deux fois.

Q: Pourquoi mid ne se déplace-t-il pas après avoir été échangé avec high ?

La valeur qui revient de high n’a jamais été lue, elle pourrait donc être un 0, un 1 ou un 2. Déplacer mid au-delà laisserait un 0 ou un 2 au milieu. Un échange avec low est différent : tout ce qui se trouve entre low et mid est un 1, donc la valeur qui revient est connue et mid peut avancer.

Q: Le tri par comptage est-il une réponse acceptable pour Sort Colors ?

Il respecte les limites de temps O(n) et d’espace O(1), et de nombreux recruteurs l’acceptent comme première réponse. Attends-toi à une question complémentaire demandant un seul parcours : il s’agit du partitionnement à trois pointeurs. Le comptage est préférable lorsqu’il y a de nombreuses couleurs, car le partitionnement ne sépare qu’en trois groupes.

MoyenDeux pointeurs Tri

+10

Vous recevez un tableau nums dans lequel chaque valeur est 0, 1 ou 2. Imaginez qu’il s’agit de trois couleurs, par exemple le rouge, le blanc et le bleu. Réorganisez le tableau de sorte que tous les 0 soient au début, puis tous les 1, puis tous les 2, et renvoyez-le.

Résolvez le problème sans utiliser de fonction de tri de bibliothèque. L’objectif est de vous servir de ce que vous savez sur les valeurs.

Fonction

sortColors(nums: integer-array) → integer-array

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 × 10⁴
Chaque nums[i] est 0, 1 ou 2.
Il se peut qu’une couleur manque et que le tableau ne contienne qu’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 celui-ci : deux 0, puis trois 1, puis deux 2.

+17 tests cachés à la soumission

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.

0 sur 3 ouverts

Solution

N’importe quel tri donne le bon ordre ; la vraie question est donc de savoir ce que les trois valeurs vous permettent d’éviter. Comme seuls 0, 1 et 2 peuvent apparaître, vous pouvez les compter et réécrire le tableau en deux passes. Avec trois pointeurs qui indiquent où se terminent les 0 et où commencent les 2, vous pouvez même placer chaque valeur à sa place en une seule passe. Cette partition en une seule passe est l’algorithme du drapeau national néerlandais.

Trier à bulles à la main

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Un tri effectué par une bibliothèque s’exécuterait en O(n log n), mais les règles du problème l’interdisent, car un recruteur veut voir ce que tu fais sachant qu’il n’y a que trois valeurs. La solution de base est donc un tri que tu écris toi-même, et le plus simple à réussir est le tri à bulles : parcourir le tableau et, chaque fois que deux éléments voisins sont dans le désordre, les échanger.

Un passage entraîne la plus grande valeur rencontrée jusqu’à la fin, comme une bulle qui remonte. Après le premier passage, la dernière position est définitive ; après le deuxième, les deux dernières le sont, et ainsi de suite, donc n-1 passages suffisent à mettre tout le tableau en ordre. Dans [2, 1, 0], le premier passage déplace le 2 à la fin, ce qui donne [1, 0, 2], et le deuxième passage échange le 1 et le 0.

Ce tri est lent, car chaque passage compare toutes les paires qui ne sont pas encore à leur place : environ n²/2 comparaisons au total. Avec n = 1.5 × 10^4, cela représente plus de 10^8 comparaisons, plus un échange pour chaque paire qui est initialement dans le désordre, et aucun de ces calculs ne tire parti du fait qu’il n’existe que trois valeurs.

Algorithme

Effectuez n-1 passages sur le tableau.
À chaque passage, comparez chaque paire de voisins nums[j] et nums[j + 1] qui n’est pas encore définitive, et échangez-les lorsque celui de gauche est plus grand.
Après le passage numéro done (en comptant à partir de 0), les dernières done + 1 positions contiennent leurs valeurs définitives, donc le passage suivant s’arrête avant celles-ci.
Renvoyez 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 nums

Comptez chaque couleur, puis réécrivez

Intuition

Le tri à bulles passe tout son temps à comparer les éléments voisins, mais tu sais déjà quelles valeurs sont présentes. Si le tableau contient deux 0, trois 1 et deux 2, le résultat est fixé avant même de déplacer quoi que ce soit : deux 0, trois 1, deux 2. Seuls les comptes comptent.

Parcours donc le tableau une fois et compte chaque valeur. Puis réécris-le depuis le début : count[0] zéros, puis count[1] uns, puis count[2] deux. C’est le tri par comptage, et il est adapté ici parce que les valeurs égales sont interchangeables. Un 1 est un 1, donc l’ordre initial n’a pas besoin d’être préservé.

Cela représente deux parcours et trois compteurs, un temps en O(n) et un espace en O(1). Cela respecte les limites, et c’est la réponse naturelle lorsqu’il y a beaucoup de couleurs. La question de suivi pour laquelle ce problème est connu est de savoir si tu peux le faire en ne parcourant le tableau qu’une seule fois.

Algorithme

Crée trois compteurs, tous à 0.
Lis chaque valeur et ajoute un à son compteur.
Écris count[0] zéros au début, puis count[1] uns, puis count[2] deux.
Retourne 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 nums

Un seul passage avec trois pointeurs (drapeau national néerlandais)

Intuition

Fais grandir trois zones pendant que tu parcours le tableau : les 0 à l’avant, les 1 juste après, les 2 à l’arrière, et une partie non parcourue entre les 1 et les 2. Trois indices marquent les frontières. Tout ce qui précède low est égal à 0, tout ce qui va de low jusqu’à, mais sans l’inclure, mid est égal à 1, tout ce qui suit high est égal à 2, et nums[mid] jusqu’à nums[high] n’a pas encore été parcouru.

Lis nums[mid]. Un 1 est déjà dans sa zone, alors avance mid. Un 0 doit aller à l’avant : échange-le avec nums[low], puis avance low et mid. La valeur qui revient de low est un 1 (ou le même 0, si aucun 1 n’a encore été rencontré), donc elle est déjà à sa place. Un 2 doit aller à l’arrière : échange-le avec nums[high] et recule high, mais laisse mid où il est, car la valeur provenant de high n’a pas encore été lue.

À chaque étape, mid avance ou high recule, donc la partie non parcourue perd une cellule à chaque fois et la boucle se termine après n étapes. Suis l’exemple avec [2, 0, 2] : le premier 2 est échangé avec le dernier 2 et high passe à 1 ; l’indice 0 contient toujours un 2, qui est échangé avec le 0 et high passe à 0 ; l’indice 0 contient maintenant le 0, qui reste en place, et tu obtiens [0, 2, 2].

Algorithme

Définissez low = 0, mid = 0 et high sur le dernier indice.
Tant que mid ≤ high, lisez nums[mid].
S’il vaut 0, échangez-le avec nums[low] et déplacez low et mid d’un pas vers la droite.
S’il vaut 1, déplacez mid d’un pas vers la droite.
S’il vaut 2, échangez-le avec nums[high] et déplacez high d’un pas vers la gauche. Laissez mid en place.
Retournez 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

La version à un seul passage est courte, et presque tous ses bogues viennent d’un pointeur qui avance alors qu’il ne devrait pas.

Avancer mid après un échange avec high. La valeur qui arrive n’a pas été lue. Dans [1, 2, 0], le 2 est échangé avec le 0, et sauter le 0 renvoie [1, 0, 2].
Parcourir la boucle tant que mid < high lorsque high est le dernier indice non lu. Quand les deux se rejoignent, cette case n’a pas encore été lue. Dans [1, 0], la boucle s’arrête avant de lire le 0 et renvoie [1, 0].
Laisser high descendre sous zéro avec un indice non signé. Un tableau ne contenant que des 2, comme [2], fait passer high à -1. En Rust, où les indices sont de type usize, gardez plutôt high une position après la partie non lue, comme le fait le code Rust.
Supposer que chaque couleur apparaît. [2, 0, 2] ne contient aucun 1, et un tableau peut ne contenir qu’une seule couleur. Les règles des pointeurs gèrent ces deux cas sans cas particuliers, alors n’en ajoutez pas.

Questions fréquentes4

Qu’est-ce que le problème du drapeau national néerlandais ?

Edsger Dijkstra l’a posé ainsi : étant donné des objets de trois couleurs disposés en ligne, le rouge, le blanc et le bleu du drapeau néerlandais, regroupez chaque couleur en un seul passage, en utilisant uniquement des échanges. Sort Colors est le même problème avec les nombres 0, 1 et 2. Sa solution est le partitionnement à trois pointeurs avec low, mid et high.

Quelle est la complexité temporelle et spatiale de Sort Colors ?

La solution en un seul passage s’exécute en temps O(n), car chaque étape réduit d’une case la partie non lue. Elle utilise un espace supplémentaire O(1) : trois indices et une valeur temporaire pour l’échange. Le tri par comptage a les mêmes bornes, mais parcourt le tableau deux fois.

Pourquoi mid ne se déplace-t-il pas après avoir été échangé avec high ?

La valeur qui revient de high n’a jamais été lue, elle pourrait donc être un 0, un 1 ou un 2. Déplacer mid au-delà laisserait un 0 ou un 2 au milieu. Un échange avec low est différent : tout ce qui se trouve entre low et mid est un 1, donc la valeur qui revient est connue et mid peut avancer.

Le tri par comptage est-il une réponse acceptable pour Sort Colors ?

Il respecte les limites de temps O(n) et d’espace O(1), et de nombreux recruteurs l’acceptent comme première réponse. Attends-toi à une question complémentaire demandant un seul parcours : il s’agit du partitionnement à trois pointeurs. Le comptage est préférable lorsqu’il y a de nombreuses couleurs, car le partitionnement ne sépare qu’en trois groupes.

Python

def sortColors(nums):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums = [2, 1, 0, 2, 0, 1, 1]

Attendu

[0, 0, 1, 1, 1, 2, 2]

Sort Colors

Fonction

Contraintes

Exemples

Indices

Solution

Trier à bulles à la main

Comptez chaque couleur, puis réécrivez

Un seul passage avec trois pointeurs (drapeau national néerlandais)

Pièges et cas limites

Questions fréquentes4

Problèmes similaires