283. 移动零

力扣题目链接 (opens new window)

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

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

示例 1:

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

示例 2:

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

提示:

• 1 <= nums.length <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

思路

这道题非常经典，是双指针入门题。

题目要求是：

• 把所有 0 移动到数组末尾
• 保持非零元素的相对顺序
• 只能在原数组上操作，不能开新数组

看完要求，很容易想暴力的做法，比如一个for循环遍历一遍不断删0元素、然后在末尾插入0元素。

但大家别忘了，数组里删除元素的时间复杂度是 O(n)，可不是O(1)。

这样的话，时间复杂度就是O(n^2)

再来看本题，我们希望做到两件事：

1. 把非零元素按顺序挪到前面
2. 多余的位置统一补 0

对于数组上的操作，如果想提效，就只能想到双指针。

双指针法（快慢指针法）：** 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。**

来看一下双指针解法：

双指针，一般都是有一个快和慢指针，对于本题，我们需要一个指针遍历整个数组，同时也需要一个指针 找到应该放非零元素的位置。

• fast：遍历整个数组
• slow：指向“下一个应该放非零元素的位置”

在遍历的时候，如果 nums[fast] != 0，说明遇到了非零元素就把它写到 slow 的位置，slow再继续向后移动。

当 nums[fast] == 0，跳过即可。

这样：所有非零元素会被按顺序写到前面，slow 指向的是“非零区的尾巴 + 1”，slow 之后全部都应该是 0

最后统一补 0 即可。

执行过程

那题目中nums = [0,1,0,3,12]数组来举例，初始化，fast与slow指针都指向起始位置。

fast 遇到 元素0，直接跳过。

遇到非零元素 1 ，将fast指针指向元素，赋值给 slow指向地址。

slow向前移动，fast向前移动。

nums[fast] == 0 ，直接跳过。

fast 遇到非零元素 3 。

将fast指针指向元素，赋值给 slow指向地址。

slow向前移动，fast向前移动。

fast 遇到非零元素 12 。

将fast指针指向元素，赋值给 slow指向地址。

slow向前移动，fast向前移动。fast此时已经结束遍历。

讲slow指向的地址，向后移动并依次赋值为0。

代码实现

C++代码

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (nums[fastIndex] != 0) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        // 将slowIndex之后的冗余元素赋值为0
        for (int i = slowIndex; i < nums.size(); i++) {
            nums[i] = 0;
        }
    }
};

以下这两行代码可以缩减成一行 nums[slowIndex++] = nums[fastIndex];

nums[slowIndex] = nums[fastIndex];
                slowIndex++;

python3

class Solution:
    def moveZeroes(self, nums):
        slow = 0
        # 把非零元素按顺序覆盖到前面
        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1

        # slow 之后全部置 0
        for i in range(slow, len(nums)):
            nums[i] = 0

Java

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;

        // 先把非零元素往前覆盖
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow++] = nums[fast];
            }
        }

        // slow 之后全部置零
        for (int i = slow; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

Go

func moveZeroes(nums []int) {
    slow := 0

    // 把非零元素覆盖到前面
    for fast := 0; fast < len(nums); fast++ {
        if nums[fast] != 0 {
            nums[slow] = nums[fast]
            slow++
        }
    }

    // slow 后全置零
    for i := slow; i < len(nums); i++ {
        nums[i] = 0
    }
}

JS

var moveZeroes = function(nums) {
    let slow = 0;

    // 把非零元素按顺序覆盖到前面
    for (let fast = 0; fast < nums.length; fast++) {
        if (nums[fast] !== 0) {
            nums[slow++] = nums[fast];
        }
    }

    // slow 后的全部补 0
    for (let i = slow; i < nums.length; i++) {
        nums[i] = 0;
    }
};

与代码随想录关系

本题与 代码随想录的 27.移除元素 (opens new window) ，基本是一个思路的。

27.移除元素 (opens new window) 使用暴力的解法，可以两层for循环，模拟数组删除元素（也就是向前覆盖）的过程。

好了，我们说一说双指针法，大家如果对双指针还不熟悉，可以看我的这篇总结双指针法：总结篇！ (opens new window)。

双指针法在数组移除元素中，可以达到O(n)的时间复杂度，在27.移除元素 (opens new window)里已经详细讲解了，那么本题和移除元素其实是一个套路。

相当于对整个数组移除元素0，然后slowIndex之后都是移除元素0的冗余元素，把这些元素都赋值为0就可以了。

如动画所示：