アルゴリズム体操7

Move zeros to left

説明

一つの整数型の配列が渡されます。
配列内の他の要素の順序を維持しながら、0に等しいすべての要素を左に移動させるアルゴリズムを実装しましょう。
次の整数配列を見てみましょう。

すべての0に等しい要素を左に移動すると、配列は次のようになります。(0以外の要素の順序を維持する必要があります)

Solution

Runtime Complexity O(n)

0の要素を配列から探す必要があります。

Memory Complexity O(1)

二つのポインター(反復子)を使うことで渡された配列のみで実装できます。

アルゴリズムの主な流れは

1. 2つのマーカーread_index と　write_indexを配列の最後の要素に配置させます。

2. read_index が 0 以上の間に

3. read_indexが「0」を指している場合は read_indexのみを減少させる。
   
   read_indexがゼロ以外を指す場合、write_indexにread_indexの要素を書き込み、write_indexとread_index の両方を減少。

4. read_indexが-1になり、ループを抜けて、現在のwrite_indexから0まで配列の要素を0にアサインしていく。
   
   

5. 完成
   

実装

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