283 - Move zeros
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.
My first attempt was to use a variable to mark the 0, that means, if it meets a zero, it will stop there and wait an element after it that is not zero. Then these two numbers will be swapped. However, this method cannot minimize the write operation since the same zero will be written into the array repeatedly. For example, z is used to mark zero, the initial state is:
0 1 0 3 12
|
z
then compare the following two methods:
1 0 0 3 12
|
z ------- 2 writes
1 3 0 0 12
|
z ------- 2 writes
1 3 12 0 0
|
z ------- 2 writes
total 6 writes
The ideal solution is:
1 0 0 3 12
|
i ------- 0 writes z = 1
1 0 0 3 12
|
i ------- 0 writes z = 2
1 0 0 3 12 1 3 0 3 12
| |
i ------- 1 write i
1 3 0 3 12 1 3 12 3 12
| |
i ------- 1 write i --- z = 2
1 3 12 0 12
|
i ------- 1 write
1 3 12 0 0
|
i ------- 1 write
total 4 writes
public void moveZeros(int[] nums){
int zeroNum = 0;
for (int i = 0; i < nums.length; i++){
if (nums[i] == 0){
zeroNum++;
}else {
if (zeroNum != 0){
nums[i - zeroNum] = nums[i];
}
}
}
for (int i = nums.length - zeroNum; i < nums.length; i++){
if (nums[i] != 0){
nums[i] = 0;
}
}
}