Informations sur le Problème

• Numéro du Problème : 283
• Nom : Déplacer les Zéros
• Difficulté : Facile
• Lien : https://leetcode.cn/problems/move-zeroes/

Description du Problème

Étant donné un tableau d'entiers nums, écrivez une fonction pour déplacer tous les 0 à la fin du tableau tout en maintenant l'ordre relatif des éléments non nuls.

Exigences :

• L'opération doit être effectuée en place, sans allocation de mémoire supplémentaire.
• Vous ne devez pas créer de copie du tableau.
• L'ordre relatif des éléments non nuls doit être préservé.

Exemples

Entrée : nums = [0,1,0,3,12]
Sortie : [1,3,12,0,0]
Explication : Les éléments non nuls [1,3,12] conservent leur ordre et sont déplacés vers l'avant, tandis que les zéros sont placés à la fin.

Entrée : nums = [0]
Sortie : [0]
Explication : Un seul élément, aucune modification nécessaire.

Entrée : nums = [1,0,2,0,3,0]
Sortie : [1,2,3,0,0,0]
Explication : L'ordre [1,2,3] est préservé. Les zéros suivants sont déplacés à la fin.

Stratégie de Résolution

Analyse Initiale

Une approche naïve consisterait à déplacer manuellement chaque zéro, ce qui serait complexe et inefficace. L'utilisation de deux pointeurs permet de parcourir le tableau une seule fois.

Méthode 1 : Échange avec Deux Pointeurs

Concept : On utilise un pointeur writePos pour indiquer la prochaine position où écrire un élément non nul, et un pointeur readPos pour parcourir le tableau. Chaque fois qu'un élément non nul est trouvé à readPos, on l'échange avec l'élément à writePos, puis on avence writePos.

Étapes de l'Algorithme :

1. Initialiser writePos = 0.
2. Pour chaque index readPos de 0 à la fin du tableau :
   • Si nums[readPos] != 0, échanger nums[writePos] et nums[readPos], puis incrémenter writePos.
3. À la fin, tous les éléments non nuls sont en tête et les zéros en queue.

Complexité :

• Temps : O(n), un seul passage.
• Espace : O(1).

Implémentation

Python :

def deplacer_zeros_vers_la_fin(tableau):
    position_ecriture = 0
    for position_lecture in range(len(tableau)):
        if tableau[position_lecture] != 0:
            # Échange simple en une ligne (Python)
            tableau[position_ecriture], tableau[position_lecture] = tableau[position_lecture], tableau[position_ecriture]
            position_ecriture += 1
    return tableau

Java :

public void deplacerZeros(int[] tableau) {
    int posEcriture = 0;
    for (int posLecture = 0; posLecture < tableau.length; posLecture++) {
        if (tableau[posLecture] != 0) {
            int temp = tableau[posEcriture];
            tableau[posEcriture] = tableau[posLecture];
            tableau[posLecture] = temp;
            posEcriture++;
        }
    }
}

Rust :

pub fn deplacer_zeros(tableau: &mut Vec<i32>) {
    let mut position_ecriture = 0;
    for position_lecture in 0..tableau.len() {
        if tableau[position_lecture] != 0 {
            tableau.swap(position_ecriture, position_lecture);
            position_ecriture += 1;
        }
    }
}</i32>

Méthode 2 : Remplacement en Deux Passes

Concept : Une variante évite les échanges inutiles. On copie d'abord tous les éléments non nuls vers l'avant du tableau dans une première passe, puis on remplit le reste avec des zéros dans une seconde passe.

Étapes de l'Algorithme :

1. Initialiser un index d'écriture idx = 0.
2. Première passe : Pour chaque élément du tableau, s'il est non nul, l'écrire à tableau[idx] et incrémenter idx.
3. Seconde passe : Remplir les positions de idx jusqu'à la fin du tableau avec des 0.

Complexité :

• Temps : O(n), deux passages séparés.
• Espace : O(1).

Implémentation

Python :

def deplacer_zeros_deux_passes(tableau):
    idx_ecriture = 0
    # Première passe : compression des non-nuls
    for valeur in tableau:
        if valeur != 0:
            tableau[idx_ecriture] = valeur
            idx_ecriture += 1
    # Seconde passe : remplissage des zéros
    for i in range(idx_ecriture, len(tableau)):
        tableau[i] = 0
    return tableau

Java :

public void deplacerZerosDeuxPasses(int[] tableau) {
    int idxEcriture = 0;
    for (int valeur : tableau) {
        if (valeur != 0) {
            tableau[idxEcriture++] = valeur;
        }
    }
    for (int i = idxEcriture; i < tableau.length; i++) {
        tableau[i] = 0;
    }
}

Rust :

pub fn deplacer_zeros_deux_passes(tableau: &mut Vec<i32>) {
    let mut idx_ecriture = 0;
    for i in 0..tableau.len() {
        if tableau[i] != 0 {
            tableau[idx_ecriture] = tableau[i];
            idx_ecriture += 1;
        }
    }
    for i in idx_ecriture..tableau.len() {
        tableau[i] = 0;
    }
}</i32>

Points Clés et Erreurs Courantes

• Préservation de l'ordre : La méthode des deux pointeurs (échange ou remplacement) garantit naturellement cet ordre, car les éléments non nuls sont traités de gauche à droite.
• Gestion des cas limites : Les solutions gèrent correctement un tableau vide, un tableau sans zéro ou un tableau composé uniquement de zéros.
• Efficacité : La méthode d'échange en un passage peut effectuer des opérations d'échange inutiles lorsque writePos == readPos (l'élément est déjà non nul). La méthode en deux passes avec remplacement direct évite ce surcoût, mais nécessite de traiter les zéros explicitement dans une seconde boucle.
• Avantage d'une passe unique : L'algorithme de pointeurs d'échange réalise le travail complet en une seule itération sur le tableau, ce qui peut être un avantage pour de très grands tableaux ou dans des contextes où le coût d'accès mémoire est critique.