283.移动零

难度：简单

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

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

示例 1:

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

示例 2:

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

提示:

• 1 <= nums.length <= 104
• -2^(31) <= nums[i] <= 2^(31) - 1

**进阶：**你能尽量减少完成的操作次数吗？

解题思路

根据 26 题的经验，当问题的条件是 数组有序 且要求 部分元素保留 的时候，可以考虑使用双指针法。

同时根据 27 题的经验，如果使用相向双指针法，虽然移动的次数少，但是会改变元素的相对位置。

因此我选择用普通的快慢指针法。

算法过程：

1. 慢指针指向新数组里非零元素应该存在的位置
2. 快指针在旧数组里，到头到尾寻找应该放入新数组里的非零元素
3. 每找到符合条件的非零元素，就用快指针指向的元素覆盖掉左指针指向的元素（注意，这里 只需覆盖，无需交换，因为两个指针速度的不同，所以慢指针所指向的位置是已经被快指针检查过的，可以放心覆盖）
4. 当快指针遍历了一遍旧数组的时候，代表新数组的非零元素已经集齐
5. 根据题目要求，新数组后面的元素必须全为0，所以慢指针需要继续往后走，并且把剩余位置全部用零来覆盖

我的代码

public void moveZeroes(int[] nums) {
    int slowIndex = 0;
    int fastIndex = 0;
    while (fastIndex < nums.length) {
        if (nums[fastIndex] != 0) {
            nums[slowIndex] = nums[fastIndex];
            slowIndex++;
        }
        fastIndex++;
    }
    while (slowIndex < nums.length) {
        nums[slowIndex] = 0;
        slowIndex++;
    }
}

时间复杂度：O(n)

空间复杂度：O(1)

一次遍历的算法

上述算法中，快慢指针各遍历了一次数组，一共遍历了两次，那么我们能不能在一次遍历中就把任务完成呢，答案是可以的。

原代码中，第二个循环，是慢指针用来填充 0 值的，但其实这部分操作可以在快指针检查原数组的时候就完成。

因为快指针检查过的部分，如果不为 0，则已经被慢指针放置在了目标位置，那么快指针指向的位置直接赋值为 0，不会影响到新数组的非 0 元素。

class Solution {
    public void moveZeroes(int[] nums) {
        int slowIndex = 0;
        int fastIndex = 0;
        while (fastIndex < nums.length) {
            if (nums[fastIndex] != 0) {
                nums[slowIndex] = nums[fastIndex];
                if (slowIndex < fastIndex) { // 当数组中只有一个元素的时候，这里可以保证快指针的赋值不影响慢指针
                    nums[fastIndex] = 0;
                }
                slowIndex++;
            }
            fastIndex++;
        }
    }
}

时间复杂度：O(n)

空间复杂度：O(1)

参考快排思想的算法

快速排序首先是要确定一个待分割的元素做 枢纽值 x，然后把所有小于等于 x 的元素放到 x 的左边，大于 x 的元素放到其右边。

那么这里，我们可以取枢纽值为 0，把不等于 0 的元素放到枢纽值的左边，等于 0 的放到其右边。

显然这是一种简化后的快速排序的思路，所以实现起来其实要简单很多。

我们使用两个指针 leftIndex 和 rightIndex，其中 leftIndex 一开始指向枢纽值左边为 0 的元素，rightIndex 则枢纽值右边寻找不为 0 的元素。

只要 nums[rightIndex] != 0，我们就交换 nums[leftIndex] 和 nums[rightIndex] 的值。

代码如下：

public void moveZeroes(int[] nums) {
    int leftIndex = 0;
    int rightIndex = 0;
    while (rightIndex < nums.length) {
        if (nums[rightIndex] != 0) {
            int temp = nums[leftIndex];
            nums[leftIndex] = nums[rightIndex];
            nums[rightIndex] = temp;
            leftIndex++;
        }
        rightIndex++;
    }
}

时间复杂度：O(n)

空间复杂度：O(1)

总结

当问题的条件是 数组有序 且要求 部分元素保留 的时候，可以考虑使用双指针法。