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,numsshould 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 solution:
后记：2019.5.11
再看当年的笔记，有几点体会，特记录一下：
- 当年还不知道Two pointer的套路，写出的代码有够暴力，居然循环嵌套循环。再不济也应该用个ArrayList记录一下非零的元素，再复制回原数组？
- 当年代码的style有点问题，操作符和变量之间没有空格。
- 当年并没有写一些文字解释自己的代码或者别人的解法，或者在code中加入注释。这样其实不利于自己深入理解代码，日后看起来也比较费力。自己以后需要多注意啊。
public class Solution {
public void moveZeroes(int[] nums) {
int counter = 0;
for(int i=0; i<nums.length-1; i++) {
if (nums[i] == 0) {
counter++;
}
}
while(counter>0){
for(int i=0; i<nums.length-1; i++) {
if (nums[i] == 0) {
nums[i] = nums[i+1];
nums[i+1] = 0;
}
}
counter--;
}
}
}
我的解法效率很低，只有3.5%
附一个高明的 code。
下面是我自己对code的理解（2019.05.11）
这个解法其实是利用了Two pointers的套路。
- index 指针的物理意义是其左边的元素为非零的元素。
- 第一个循环结束后，所有的非零元素都被放到了index左边。第二个循环将index到数组末端的元素设置为零即可。
public class Solution {
public void moveZeroes(int[] nums) {
int index = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[i] != 0){
nums[index++] = nums[i];
}
}
for(int i = index; i < nums.length; i++) {
nums[i] = 0;
}
}
}
效率是87.33%, unbelievable.
