Move zeros to left

설명

하나의 정수형 배열이 전달됩니다.
배열에서 다른 요소의 순서를 유지하면서 0과 같은 모든 요소를 ​​왼쪽으로 이동시키는 알고리즘을 구현합시다.
다음 정수 배열을 살펴 보겠습니다.



모든 0과 같은 요소를 왼쪽으로 이동하면 배열은 다음과 같습니다. (0이 아닌 요소의 순서를 유지해야 함)

Solution

Runtime Complexity O(n)

0 요소를 배열에서 찾아야합니다.

Memory Complexity O(1)

두 개의 포인터 (반복자)를 사용하여 전달 된 배열에서만 구현할 수 있습니다.

알고리즘의 주요 흐름은

2 개의 마커 read_index 와 write_index 를 배열의 마지막 요소에 배치시킵니다.

read_index가 0 이상일 때

read_index가 '0'을 가리키면 read_index만 감소합니다.

read_index가 제로 이외를 가리키는 경우, write_index에 read_index의 요소를 기입해, write_index와 read_index의 양쪽 모두를 감소.

read_index가 -1이 되어 루프를 빠져 현재의 write_index로부터 0까지 배열의 요소를 0에 할당해 간다.

완성

구현

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