Gymnastique algorithmique 7

Move zeros to left

La description

Un tableau de type entier est passé. Implémentons un algorithme qui déplace tous les éléments égaux à 0 vers la gauche tout en conservant l'ordre des autres éléments du tableau. Jetez un œil au tableau d'entiers suivant.

En déplaçant tous les éléments égaux à zéro vers la gauche, le tableau ressemble à ceci: (Doit garder l'ordre des éléments non nuls)

Solution

Runtime Complexity O(n) Vous devez trouver l'élément 0 dans le tableau. Memory Complexity O(1) Il ne peut être implémenté qu'avec le tableau passé en utilisant deux pointeurs (répéteurs).

Le flux principal de l'algorithme est

1. Placez les deux marqueurs read_index et write_index sur le dernier élément du tableau.

2. Tant que read_index est égal ou supérieur à 0

3. Si read_index pointe sur "0", ne décrémentez que read_index. <img width = "594" alt = "Capture d'écran 2019-12-20 à 17.58.40.png " src = "https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0" /405022/e6fc1c0e-cc76-b5b6-44f7-764ead2af83a.png "> Si read_index pointe vers une valeur différente de zéro, écrivez l'élément read_index dans write_index et décrémentez à la fois write_index et read_index. <img width = "564" alt = "Capture d'écran 2019-12-20 à 17.59.59.png " src = "https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0" /405022/6b20aea1-b27b-2a3d-344d-dee0eda0c1d4.png ">

4. Le read_index devient -1, quittez la boucle et affectez les éléments du tableau à 0 à partir de write_index actuel à 0.

5. Achèvement

la mise en oeuvre

moveZeroToLeft.java

public class moveZerosToLeft {
    public void move_zeros_to_left_in_array(int[] A) {

        int readIndex = A.length - 1;
        int writeIndex = A.length -1;

        while (readIndex >= 0) {

            if (A[readIndex] != 0) {
                A[writeIndex] = A[readIndex];
                writeIndex--;
            }
            readIndex--;
        }

       while (writeIndex >= 0) {
           A[writeIndex] = 0;
           writeIndex--;
       }
    }
}

Mina.java

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        // write your code here
        moveZerosToLeft algorithm = new moveZerosToLeft();

        int[] v = new int[]{1, 10, -1, 11, 5, 0, -7, 0, 25, -35};
        System.out.println("Original Array: " + Arrays.toString(v));
        algorithm.move_zeros_to_left_in_array(v);
        for (int item : v) {
            System.out.print(item + ", ");
        }
    }
}

Output