数组 - LeetCode 283. 移动零

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

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

输入: nums = [0]
输出: [0]

方法1:两次遍历

• 先统计非0元素
• 剩余都补0
• 时间复杂度: O(n) 空间复杂度: O(1)

class Solution {
    public void moveZeroes(int[] nums) {
       if(nums==null) {
        return;
    }
        // 先统计非0元素
        int index = 0;
        for(int i=0; i<nums.length;i++) {
            if(nums[i] != 0) {
                nums[index] = nums[i];
                index++;
            }
        }
        //非0元素统计完了，剩下的都是0了
        for(int i=index; i<nums.length;i++) {
            nums[i] = 0;
        }
    }
}

方法2: 一次遍历
时间复杂度: O(n) 空间复杂度: O(1)

参考快排的思想：

• 首先确定一个待分割的元素做中间点x，然后把所有小于等于x的元素放到x的左边，大于x的元素放到其右边。
• 这里可用0做中间点，把不等于0(注意题目没说不能有负数)的放到中间点的左边，等于0的放到其右边。

这的中间点就是0本身，所以实现起来比快排简单很多: 使用两个指针i和j，只要nums[i] != 0，就交换nums[i]和nums[j]

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums==null) {
            return;
        }
        // 两个指针i和j
        int j = 0;
        for(int i=0;i<nums.length;i++) {
            // 当前元素!=0，就把其交换到左边，等于0的交换到右边
            if(nums[i]!=0) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j++] = tmp;
            }
        }
    }
}