Analyse des décalages de zéros 0️⃣

Dans les commentaires, vous avez présenté presque toutes les façons possibles de résoudre le problème.

Bien sûr, le modèle classique pour résoudre ce problème est celui des deux pointeurs.
Voici la solution idéale avec une complexité O(n) en temps et O(1) en mémoire :

def move_zeroes(nums: list[int]) -> None:
    insert_pos = 0
    
    for i in range(len(nums)):
        if nums[i] != 0:
            # Échange l'élément non nul avec le zéro "à gauche"
            nums[insert_pos], nums[i] = nums[i], nums[insert_pos]
            insert_pos += 1


Pas d'allocations. Pas de pop() au milieu de la liste. On parcourt le tableau exactement une fois. La variable insert_pos pointe toujours vers le premier zéro disponible. Dès qu'on trouve un nombre différent de zéro, on les échange simplement grâce au mécanisme intégré de décompression de tuples en Python.

🐍 Mais ce ne serait pas intéressant sans quelque chose de plus astucieux. Voici un flex pythonique en une ligne sans générateurs :
nums.sort(key=bool, reverse=True)


Comment ça marche ? bool(0) donne False, les autres nombres donnent True. Le tri intégré Timsort en Python est stable — il conserve strictement l'ordre initial des éléments égaux. Tous les True (nombres) se déplaceront à gauche, en conservant leur ordre, et tous les False (zéros) fileront à droite.

Oui, formellement la complexité est O(n log n), ce qui est algorithmiquement moins bon que les deux pointeurs. Mais comme Timsort est écrit en C ultra-optimisé, sur des listes réelles de petite taille, ce code surpassera physiquement les boucles en Python pur en termes de vitesse d'exécution.

#algosdev