Déplacer les valeurs non nulles vers la droite : un problème d'entretien de tableau courant-2

Introduction

Dans cet article, nous allons explorer comment décaler toutes les valeurs non nulles d'un tableau vers la droite tout en conservant leur ordre relatif. Ce problème est une question d'entretien courante qui teste votre compréhension de la manipulation des tableaux et de l'optimisation des algorithmes. Plongeons dans la solution utilisant Java.

Si vous n'êtes pas familier avec les concepts de base des tableaux, je vous recommande de consulter Comprendre les bases des tableaux en Java : un guide simple pour vous mettre à jour !

Énoncé du problème

Étant donné un tableau d'entiers, nous souhaitons décaler toutes les valeurs non nulles vers la droite tout en préservant leur ordre. Les valeurs zéro doivent être déplacées vers la gauche.

Exemple :

Input: [1, 2, 0, 3, 0, 0, 4, 0, 2, 9]
Output: [0, 0, 0, 0, 1, 2, 3, 4, 2, 9]

Approche

Nous utiliserons une approche de suivi d'index pour résoudre ce problème. Le but est de parcourir le tableau de droite à gauche et de déplacer les éléments non nuls vers leurs positions correctes.

1. Initialiser un pointeur : Commencez par définir un pointeur sur le dernier index du tableau. Ce pointeur marquera l'endroit où la prochaine valeur non nulle doit être placée.
2. Parcourir le tableau : Déplacez-vous dans le tableau de droite à gauche. Pour chaque élément non nul rencontré, placez-le à la position indiquée par le pointeur et décrémentez le pointeur.
3. Zéros restants : Une fois que tous les éléments non nuls ont été repositionnés, tous les points inutilisés au début du tableau (c'est-à-dire à gauche du pointeur) contiendront automatiquement des zéros.

Cette approche a une complexité temporelle de O(n) et une complexité spatiale de O(1), ce qui la rend à la fois efficace et peu encombrante.

Mise en œuvre

package arrays;

// Time Complexity - O(n)
// Space Complexity - O(1)
public class ShiftNonZeroValuesToRight {

    private void shiftValues(int[] inputArray) {

        /* Variable to keep track of index position to be 
           filled with Non-Zero Value */
        int pointer = inputArray.length - 1;

        // If value is Non-Zero then place it at the pointer index
        for (int i = pointer; i >= 0; i--) {

            /* If there is a non-zero already at correct position,
               just decrement position */
            if (inputArray[i] != 0) {

                if (i != pointer) {
                    inputArray[pointer] = inputArray[i];
                    inputArray[i] = 0;
                }

                pointer--;
            }
        }

        // Printing result using for-each loop
        for (int i : inputArray) {
            System.out.print(i);
        }

        System.out.println();

    }

    public static void main(String[] args) {

        // Test-Case-1 : Ending with a Non-Zero
        int input1[] = { 1, 2, 0, 3, 0, 0, 4, 0, 2, 9 };

        // Test-Case-2 : Ending with Zero
        int input2[] = { 8, 5, 1, 0, 0, 5, 0 };

        // Test-Case-3 : All Zeros
        int input3[] = { 0, 0, 0, 0 };

        // Test-Case-4 : All Non-Zeros
        int input4[] = { 1, 2, 3, 4 };

        // Test-Case-5 : Empty Array
        int input5[] = {};

        // Test-Case-6 : Empty Array
        int input6[] = new int[5];

        // Test-Case-7 : Uninitialized Array
        int input7[];

        ShiftNonZeroValuesToRight classObject = new ShiftNonZeroValuesToRight();
        classObject.shiftValues(input1); // Result : 0000123429
        classObject.shiftValues(input2); // Result : 0008515
        classObject.shiftValues(input3); // Result : 0000
        classObject.shiftValues(input4); // Result : 1234
        classObject.shiftValues(input5); // Result :
        classObject.shiftValues(input6); // Result : 00000
        classObject.shiftValues(input7); // Result : Compilation Error - Array may not have been initialized

    }
}

Explication du Code

1. Méthode shiftValues :
   • Paramètre d'entrée : inputArray – Le tableau qui doit être traité.
   • Initialisation du pointeur : le pointeur est initialisé au dernier index du tableau.
   • Array Traversal : La boucle parcourt la fin du tableau vers le début, en vérifiant les éléments non nuls. Les éléments non nuls sont déplacés vers la position indiquée par le pointeur et le pointeur est décrémenté.
   • Résultat : Une fois que tous les éléments non nuls sont déplacés, les éléments restants du tableau seront naturellement des zéros sans aucune étape supplémentaire.
2. Méthode principale :
   • La méthode principale contient divers cas de test pour démontrer différents scénarios, tels que des tableaux se terminant par une valeur non nulle ou nulle, des tableaux avec tous des zéros ou tous des non-zéros, des tableaux vides et des tableaux non initialisés.

Cas extrêmes pris en compte

• Tableaux vides : Le programme gère les tableaux vides sans lever d'exception.

• Tableaux non initialisés : Décommenter le scénario de test pour les tableaux non initialisés entraînera une erreur de compilation, démontrant l'importance de l'initialisation du tableau.

Conclusion

Ce programme fournit un moyen efficace de décaler des valeurs non nulles vers la droite dans un tableau. C'est un excellent exemple de la façon dont une gestion minutieuse des pointeurs peut conduire à des solutions optimales en termes de complexité temporelle et spatiale.

Pour une autre question d'entretien courante sur les tableaux, consultez mon article précédent sur le déplacement des valeurs non nulles vers la gauche : un problème d'entretien de tableau courant-1

Si vous avez des questions ou des suggestions, n'hésitez pas à laisser un commentaire ci-dessous. Bon codage !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!