题目大意

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明：
1.必须在原数组上操作，不能拷贝额外的数组。
2.尽量减少操作次数。

方法一

从数组的第0个元素从头查找，当遇到0时(如nums[i])，就查找往后的第一个非零元素nums[j],然后交换这两个元素。这样做的时间复杂度为O(n^2)。

public void moveZeroes(int[] nums) {
         for(int i=0;i<nums.length;i++)
        {
            if(nums[i]==0)
            {
                int replace = find_replace_pos(nums,i);
                if(replace==i) return;
                int temp = nums[i];
                nums[i] = nums[replace];
                nums[replace] = temp;
            }
        }
    }
private int find_replace_pos(int[] nums,int start) {
        for(int j=start+1;j<nums.length;j++)
            if(nums[j]!=0) return j;
        return start;
    }

运行时间41ms,击败11.48%。

方法二：快慢指针

设置i,j两个指针，当j遇到0时，持续向后移动。当i遇到0时，停止移动。

 public void moveZeroes(int[] nums) {
        for(int i=0,j=0;j<nums.length;) { //第一个0元素
            while(i<nums.length && nums[i]!=0) {
                ++i;
                ++j;
            } 
            while(j<nums.length && nums[j]==0) ++j;
            if(i>=nums.length || j>=nums.length) break;
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] =temp;
        }
    }

运行时间2ms,击败29.63%。

方法三：count移位

维护一个count变量，记录当前发现0的次数，然后依次将num[i]向前移动到相应的位置。

 public void moveZeroes(int[] nums) {
        int cnt = 0;
        for(int i=0;i<nums.length;i++)
        {
            if(nums[i]==0) ++cnt;
            else nums[i-cnt] = nums[i];
        }
        for(int i=nums.length-cnt;i<nums.length;i++)
            nums[i]=0;
    }

运行时间1ms,击败96.97%。