アルゴリズム体操7
Move zeros to left
説明
一つの整数型の配列が渡されます。
配列内の他の要素の順序を維持しながら、0に等しいすべての要素を左に移動させるアルゴリズムを実装しましょう。
次の整数配列を見てみましょう。
すべての0に等しい要素を左に移動すると、配列は次のようになります。(0以外の要素の順序を維持する必要があります)
Solution
Runtime Complexity O(n)
0の要素を配列から探す必要があります。
Memory Complexity O(1)
二つのポインター(反復子)を使うことで渡された配列のみで実装できます。
アルゴリズムの主な流れは
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
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--;
}
}
}
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 + ", ");
}
}
}
Author And Source
この問題について(アルゴリズム体操7), 我々は、より多くの情報をここで見つけました https://qiita.com/yutakihara/items/521e6127ff99c5196bce著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .