Algorithmusgymnastik 7

Move zeros to left

Erläuterung

Ein Array vom Typ Integer wird übergeben. Implementieren wir einen Algorithmus, der alle Elemente gleich 0 nach links verschiebt, während die Reihenfolge der anderen Elemente im Array beibehalten wird. Schauen Sie sich das folgende Integer-Array an.

Wenn Sie alle Elemente mit dem Wert Null nach links verschieben, sieht das Array folgendermaßen aus: (Muss die Reihenfolge der Nicht-Null-Elemente beibehalten)

Solution

Runtime Complexity O(n) Sie müssen das 0-Element im Array finden. Memory Complexity O(1) Es kann nur mit dem Array implementiert werden, das mit zwei Zeigern (Repetitoren) übergeben wird.

Der Hauptfluss des Algorithmus ist

1. Platzieren Sie die beiden Markierungen read_index und write_index auf dem letzten Element des Arrays. <img width = "593" alt = "Screenshot 2019-12-20 at 17.57.38.png " src = "https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0" /405022/4eb6fef7-29d6-0684-1a39-91df7a6d3f80.png ">

2. Während read_index 0 oder höher ist

3. Wenn read_index auf "0" zeigt, dekrementieren Sie nur read_index. <img width = "594" alt = "Screenshot 2019-12-20 at 17.58.40.png " src = "https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0" /405022/e6fc1c0e-cc76-b5b6-44f7-764ead2af83a.png "> Wenn read_index auf einen Wert ungleich Null zeigt, schreiben Sie ein Element von read_index in write_index und dekrementieren Sie sowohl write_index als auch read_index. <img width = "564" alt = "Screenshot 2019-12-20 at 17.59.59.png " src = "https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0" /405022/6b20aea1-b27b-2a3d-344d-dee0eda0c1d4.png ">

4. Der read_index wird zu -1, verlässt die Schleife und weist die Elemente des Arrays 0 zu, vom aktuellen write_index 0.

5. Fertigstellung

Implementierung

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