Move Zeroes

Q: Comment déplacer les zéros à la fin sans modifier l’ordre des autres éléments ?

Conservez un index write pour le prochain emplacement libre au début et parcourez le tableau avec un deuxième index. Chaque valeur non nulle trouvée est échangée avec l’emplacement write , puis write avance d’une position vers la droite. Les valeurs sont placées dans l’ordre où vous les trouvez, leur ordre relatif ne change donc jamais.

FacileDeux pointeurs

+10

Vous recevez un tableau d’entiers nums. Déplacez tous les 0 à la fin du tableau et conservez les autres valeurs dans l’ordre où elles se trouvaient. Renvoyez le tableau réorganisé, qui a la même longueur que nums.

Fonction

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

numsinteger-array: le tableau d’entiers à réorganiser
Renvoieinteger-array: les nombres avec les valeurs non nulles d’abord, dans leur ordre d’origine, et tous les 0 à la fin

Contraintes

1 ≤ nums.length ≤ 5000
-10⁵ ≤ nums[i] ≤ 10⁵

Exemples

Entrée: nums = [0, 4, 0, 7, 2]
Sortie: [4, 7, 2, 0, 0]
Explication: Les valeurs qui ne sont pas 0 sont 4, 7 et 2, et elles conservent cet ordre au début. Les deux 0 occupent les deux dernières places.

+14 tests cachés à la soumission

Pour aller plus loin

Peux-tu plutôt déplacer tous les 0 au début, en conservant les autres valeurs dans leur ordre, en un seul passage avec une mémoire supplémentaire de O(1) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Placer les zéros à la fin n’est pas la partie difficile. C’est conserver les autres valeurs dans leur ordre d’origine qui l’est, et cela exclut d’échanger chaque 0 avec le dernier élément. Divise le tableau en une zone avant qui contient les valeurs non nulles trouvées jusqu’ici et le reste. Un index lit chaque élément, un deuxième indique où doit se trouver la prochaine valeur non nulle, et un seul parcours suffit pour terminer le travail sur place.

Copiez les valeurs non nulles

Intuition

Construis un nouveau tableau. Parcours nums et copie chaque valeur différente de 0, dans l’ordre où tu la rencontres. Ajoute ensuite des zéros jusqu’à ce que le nouveau tableau soit aussi long que nums. Le nombre de zéros que tu ajoutes correspond au nombre de valeurs ignorées.

Pour [0, 4, 0, 7, 2], l’étape de copie donne [4, 7, 2], et deux zéros donnent [4, 7, 2, 0, 0]. L’ordre est correct parce que tu copies les valeurs dans l’ordre où tu les lis.

Chaque élément est lu une fois et écrit une fois, donc le temps d’exécution est en O(n). Le deuxième tableau nécessite O(n) mémoire, ce que l’approche suivante évite.

Algorithme

Créez un tableau de résultats vide.
Pour chaque valeur de nums, ajoutez-la au résultat si elle n’est pas égale à 0.
Ajoutez des zéros jusqu’à ce que le résultat contienne autant d’éléments que nums.
Retournez le résultat.

def moveZeroes(nums):
    result = [x for x in nums if x != 0]
    result += [0] * (len(nums) - len(result))
    return result

Deux pointeurs, échange en place

Intuition

Utilise deux indices. read parcourt chaque élément de gauche à droite. write indique où doit se trouver la prochaine valeur non nulle. Après chaque étape, deux faits sont vérifiés : tout ce qui précède write correspond aux valeurs non nulles rencontrées jusqu’ici, dans leur ordre d’origine, et tout ce qui se trouve entre write et read vaut 0.

Lorsque nums[read] n’est pas égal à 0, échange-le avec nums[write] et déplace write d’un cran vers la droite. La valeur qui arrive à l’indice read est un 0 de la zone des zéros, ou la même valeur lorsque les deux indices sont égaux. Les valeurs non nulles ne font que passer par-dessus les zéros, jamais les unes par-dessus les autres : leur ordre est donc conservé.

Avec [0, 4, 0, 7, 2] : le 4 à l’indice 1 est échangé avec l’élément à l’indice 0, ce qui donne [4, 0, 0, 7, 2]. Le 7 à l’indice 3 est échangé avec l’élément à l’indice 1, ce qui donne [4, 7, 0, 0, 2]. Le 2 à l’indice 4 est échangé avec l’élément à l’indice 2, ce qui donne [4, 7, 2, 0, 0]. Un seul passage et aucun deuxième tableau : temps O(n) et mémoire O(1).

Algorithme

Définis write à 0.
Déplace read du premier indice au dernier.
Si nums[read] n’est pas égal à 0, échange nums[read] avec nums[write], puis ajoute 1 à write.
Renvoie nums.

def moveZeroes(nums):
    write = 0  # nums[:write] holds the non-zero values found so far, in order
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

Pièges et cas limites

Les erreurs habituelles perturbent soit l’ordre des autres valeurs, soit ignorent des éléments.

Échanger chaque 0 avec le dernier élément déplace les zéros, mais mélange le reste : [0, 4, 7] devient [7, 4, 0].
Supprimer les zéros du tableau pendant qu’un index le parcourt fait ignorer des éléments. Dans [0, 0, 5], la suppression à l’index 0 fait glisser le deuxième 0 à l’index 0, tandis que la boucle passe à l’index 1. Chaque suppression décale également le reste du tableau, ce qui rend la boucle O(n²).
Teste x != 0, et non x > 0. Les valeurs négatives ne sont pas des zéros : [-1, 0, -2] doit devenir [-1, -2, 0], mais avec x > 0, la version avec copie renvoie [0, 0, 0].
Un tableau sans zéros, ou contenant uniquement des zéros, doit rester inchangé. Dans la version avec échange, read et write restent égaux jusqu’au premier 0 ; ces échanges ne changent donc rien.
En Lua et en R, les tableaux commencent à 1, donc write commence aussi à 1.

Questions fréquentes4

Quelle est la complexité temporelle de Move Zeroes ?

O(n). Les deux approches parcourent chaque élément une seule fois. Copier les valeurs non nulles dans un nouveau tableau nécessite O(n) de mémoire supplémentaire, tandis que l’échange avec deux pointeurs s’effectue dans le tableau avec O(1) de mémoire supplémentaire.

Comment déplacer les zéros à la fin sans modifier l’ordre des autres éléments ?

Conservez un index write pour le prochain emplacement libre au début et parcourez le tableau avec un deuxième index. Chaque valeur non nulle trouvée est échangée avec l’emplacement write, puis write avance d’une position vers la droite. Les valeurs sont placées dans l’ordre où vous les trouvez, leur ordre relatif ne change donc jamais.

Peut-on déplacer les zéros en effectuant moins d’écritures ?

Oui. Au lieu d’échanger les valeurs, copiez chaque valeur non nulle dans nums[write], puis, après le parcours, remplissez de 0 toutes les positions de write jusqu’à la fin. Ainsi, chaque position est écrite au plus une fois. Vous pouvez également éviter un échange lorsque read est égal à write, car cela remettrait une valeur à l’endroit où elle se trouve déjà.

Pourquoi Move Zeroes est-il un problème à deux pointeurs ?

Un pointeur lit chaque élément et l’autre marque la fin de la partie avant déjà traitée. Les deux avancent uniquement, ce qui leur permet de parcourir le tableau en un seul passage. Le même schéma de lecture et d’écriture permet de supprimer les doublons d’un tableau trié ou d’en filtrer une valeur sur place.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums = [0, 4, 0, 7, 2]

Attendu

[4, 7, 2, 0, 0]