Given arrays of
0s and nonzeros. Shift zeros to left and non-zeros to right.
For example,
0 9 2 6 0 1 7 8 0 0 9
Take a variable
and assign it first non-zero position.
Position = 1
here, since elements in array starts from 0.
Next start
other counter from position + 1, goto till end, if you find any zero element,
swap it with position, increment position by 1 repete this logic until, you
reach end of the array.
Algorithm
like below.
Step 1: in arr[], i, position.
Step 2: find first non-zero position.
for(i = 0; i<arr.length;
i++){
if(a[i] != 0){
position = i;
break;
}
}
Step 3: for(i = position + 1; i < arr.length; i++){
if(a[i] != 0){
continue;
}
swap(a[i], a[position]);
position++;
}
For the
above example, following is the sequence for every swapping.
Step 1: 0 9 2 6 0 1 7 8 0 0 9 (Initial position = 1, i = 2)
Step 2: 0 0 2 6 9 1 7 8 0 0 9 (After swapping position = 2,
i = 5)
Step 3: 0 0 0 6 9 1 7 8 2 0 9 (After swapping position=3, i=8)
Step 4: 0 0 0 0 9 1 7 8 2 6 9
Following is
the complete application.
import java.util.Objects; public class MoveZeros { public static void moveZeros(int arr[]) { Objects.requireNonNull(arr); if (arr.length < 2) return; int position = -1; for (int j = 0; j < arr.length; j++) if (arr[j] != 0) { position = j; break; } for (int j = position + 1; j < arr.length; j++) { if (arr[j] != 0) continue; int temp = arr[j]; arr[j] = arr[position]; arr[position] = temp; position++; } } }
Following
are the junit test cases.
import static org.junit.Assert.assertTrue; import java.util.Arrays; import org.junit.Test; public class MoveZerosTest { @Test public void test1() { int arr[] = { 0, 9, 2, 6, 0, 1, 7, 8, 0, 0, 9 }; int expected[] = { 0, 0, 0, 0, 9, 1, 7, 8, 2, 6, 9 }; MoveZeros.moveZeros(arr); assertTrue(Arrays.equals(arr, expected)); int[] arr1 = { 0, 0, 0, 0, 0, 0, 5, 6, 7, 0 }; int[] expected1 = { 0, 0, 0, 0, 0, 0, 0, 6, 7, 5 }; MoveZeros.moveZeros(arr1); assertTrue(Arrays.equals(arr1, expected1)); int[] arr2 = { 5, 6, 7, 8, 0, 0, 0 }; int[] expected2 = { 0, 0, 0, 8, 5, 6, 7 }; MoveZeros.moveZeros(arr2); assertTrue(Arrays.equals(arr2, expected2)); int[] arr3 = { 0, 5 }; int[] expected3 = { 0, 5 }; MoveZeros.moveZeros(arr3); assertTrue(Arrays.equals(arr3, expected3)); int[] arr4 = { 5, 0 }; int[] expected4 = { 0, 5 }; MoveZeros.moveZeros(arr4); assertTrue(Arrays.equals(arr4, expected4)); } @Test public void test2() { int arr[] = {}; int expected[] = {}; MoveZeros.moveZeros(arr); assertTrue(Arrays.equals(arr, expected)); } @Test(expected = NullPointerException.class) public void test3() { MoveZeros.moveZeros(null); } }
No comments:
Post a Comment