Déplacement des valeurs non nulles vers la gauche : un problème d'entretien de tableau courant-1

Introduction

Lors des entretiens techniques, des problèmes de manipulation de tableaux sont fréquemment rencontrés. Dans cet article, nous aborderons un problème courant : Décaler les valeurs non nulles vers la gauche tout en conservant l'ordre des éléments non nuls et en poussant tous les zéros vers la droite.

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, votre tâche consiste à déplacer tous les éléments non nuls vers la gauche tout en poussant tous les éléments nuls vers la droite. L'ordre relatif des éléments non nuls doit être conservé.

Exemple :

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

Approche

Nous pouvons résoudre ce problème en temps O(n) en utilisant un seul passage à travers le tableau, et la solution aura une complexité spatiale de O(1).

1. Utilisez un pointeur pour suivre l'index du prochain élément non nul.
2. Parcourez le tableau en plaçant des éléments non nuls à l'index du pointeur.
3. Incrémentez le pointeur à chaque fois qu'un élément non nul est placé.

Le code

package arrays;

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

    private void shiftValues(int[] inputArray) {

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

        // If value is Non-Zero then place it at the pointer index
        for (int i = 0; i < inputArray.length; i++) {

            /* If there is a non-zero already at correct position, 
                     just increment 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 : Starting with a Non-Zero
        int input1[] = { 1, 2, 0, 3, 0, 0, 4, 3, 2, 9 };

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

        // 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[];

        ShiftNonZeroValuesToLeft classObject = new ShiftNonZeroValuesToLeft();
        classObject.shiftValues(input1); // Result : 1234329000
        classObject.shiftValues(input2); // Result : 5129000
        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

• La méthode shiftValues parcourt le tableau d'entrée.

• Si une valeur non nulle est trouvée, elle est placée à l'index du pointeur actuel et l'élément à l'index actuel est remplacé par 0.

• Le pointeur est ensuite incrémenté pour suivre la position suivante pour un élément non nul.

• S'il y a déjà une valeur non nulle à la bonne position (c'est-à-dire à l'index du pointeur), la méthode incrémente simplement le pointeur sans effectuer aucun échange.

• Cela continue jusqu'à ce que l'ensemble du tableau soit traité.

Complexité temporelle et spatiale

• Complexité temporelle : O(n), où n est la longueur du tableau.

• Complexité spatiale : O(1), puisque nous modifions le tableau en place.

Cas de pointe

• Tous les zéros : Si le tableau contient tous les zéros, il restera inchangé.

• Pas de zéros : S'il n'y a pas de zéros, l'ordre original des éléments est conservé.

• Tableau vide : La fonction devrait gérer les tableaux vides sans problème.

Conclusion

Ce problème montre l'importance de comprendre les techniques de manipulation de tableaux et leur efficacité dans le codage des entretiens. La maîtrise de tels problèmes peut grandement améliorer vos compétences en résolution de problèmes !

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!