[JAVA] 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.

Screen Shot 2019-12-20 at 17.42.26.png

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)

Screen Shot 2019-12-20 at 17.44.09.png

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. Screen Shot 2019-12-20 at 17.57.38.png

  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 "> Screen Shot 2019-12-20 at 17.59.16.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. Screen Shot 2019-12-20 at 18.02.31.png Screen Shot 2019-12-20 at 18.03.14.png

  5. Achèvement Screen Shot 2019-12-20 at 18.03.32.png

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 Screen Shot 2019-12-20 at 18.06.27.png

Recommended Posts

Gymnastique algorithmique 12
Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique algorithmique 23 Intervalles de fusion
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Exercice d'algorithme 6
Gymnastique algorithmique 24 Inverser une liste liée
Algorithme Python
Exercices d'algorithme 13
Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Gymnastique algorithmique 24 Milieu de la liste liée
Mémorandum Python (algorithme)
Algorithme d'apprentissage du dictionnaire
Algorithme de recherche de chaînes