移动零 | 秋招知识库

方法一：把 nums 当作栈

用一个栈记录非零元素。

看示例 1， $nums = [0, 1, 0, 3, 12]$ 。

$i$	$nums [i]$	$nums [i]$ 是否入栈	栈
$0$	$0$	否	$[]$
$1$	$1$	是	$[1]$
$2$	$0$	否	$[1]$
$3$	$3$	是	$[1, 3]$
$4$	$12$	是	$[1, 3, 12]$

最后，在栈的末尾添加两个 $0$ ，即为答案 $[1, 3, 12, 0, 0]$ 。

为了做到 $O (1)$ 空间复杂度，直接把 $nums$ 当作栈，用一个变量 $stackSize$ 表示栈的大小，初始值为 $0$ 。

入栈就是把 $nums [stackSize]$ 置为 $nums [i]$ ，然后把 $stackSize$ 加一。

最后把 $nums$ 中的下标从 $stackSize$ 到 $n - 1$ 的数都置为 $0$ 。

Python 解法1C++ 解法1

python

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        stack_size = 0
        for x in nums:
            if x:
                nums[stack_size] = x  # 把 x 入栈
                stack_size += 1
        for i in range(stack_size, len(nums)):
            nums[i] = 0

cpp

// C++ 版待补充

Python 解法2C++ 解法2

python

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        stack_size = 0
        for x in nums:
            if x:
                nums[stack_size] = x  # 把 x 入栈
                stack_size += 1
        nums[stack_size:] = [0] * (len(nums) - stack_size)

cpp

// C++ 版待补充

C++ 解法3

cpp

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int stack_size = 0;
        for (int x : nums) {
            if (x) {
                nums[stack_size++] = x; // 把 x 入栈
            }
        }
        fill(nums.begin() + stack_size, nums.end(), 0);
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是 $nums$ 的长度。
空间复杂度： $O (1)$ 。

方法二：双指针+交换元素

方法一在最坏情况下（ $nums$ 全为 $0$ ），需要遍历 $nums$ 两次。能否做到一次遍历？

核心思路

把 $0$ 视作空位。我们要把所有非零元素都移到数组左边的空位上，并保证非零元素的顺序不变。

例如 $nums = [0, 0, 1, 2]$ ，把 $1$ 放到最左边的空位上，数组变成 $[\underset{―}{1}, 0, \underset{―}{0}, 2]$ 。注意 $1$ 移动过去后，在原来 $1$ 的位置又产生了一个新的空位。也就是说，我们交换了 $nums [0] = 0$ 和 $nums [2] = 1$ 这两个数。

为了保证非零元素的顺序不变，我们需要维护最左边的空位的位置（下标）。

具体思路

从左到右遍历 $nums [i]$ 。

同时维护另一个下标 ${start}_{0}$ （初始值为 $0$ ），并保证下标区间 $[{start}_{0}, i - 1]$ 都是空位（ $0$ ），且 ${start}_{0}$ 指向最左边的空位。

每次遇到 $nums [i] \neq 0$ 的情况，就把 $nums [i]$ 移动到最左边的空位上，也就是交换 $nums [i]$ 和 $nums [{start}_{0}]$ 。交换后把 ${start}_{0}$ 和 $i$ 都加一，从而使【 $[{start}_{0}, i - 1]$ 都是空位】这一性质仍然成立。

如果 $nums [i] = 0$ ，无需交换，只把 $i$ 加一。

示例 1 的 $nums = [0, 1, 0, 3, 12]$ ，计算过程如下（下划线表示交换的两个数）：

$i$	${start}_{0}$	$nums [i]$	操作后
$0$	$0$	$0$	不操作
$1$	$0$	$1$	$[\underset{―}{1}, \underset{―}{0}, 0, 3, 12]$
$2$	$1$	$0$	不操作
$3$	$1$	$3$	$[1, \underset{―}{3}, 0, \underset{―}{0}, 12]$
$4$	$2$	$12$	$[1, 3, \underset{―}{12}, 0, \underset{―}{0}]$

由于每次操作后， $[{start}_{0}, i - 1]$ 对应的元素值全为 $0$ 这一性质始终成立，所以 $nums$ 遍历结束后（ $i = n$ ）， $[{start}_{0}, n - 1]$ 对应的元素值全为 $0$ ，且 $[0, {start}_{0} - 1]$ 都是交换过去的非零元素，这样就满足了题目「将所有 $0$ 移动到数组的末尾」的要求。

答疑

问：如果 $nums$ 的前几个数都不是 $0$ 呢？

答： ${start}_{0}$ 会和 $i$ 同时向右移动，直到遇到 $0$ （或者到达数组末尾）为止。

Python 解法4C++ 解法4

python

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        循环不变量：在循环过程中，nums 的数据分布始终如下图
        [ 非零元素 | 零元素 | 尚未遍历 ]
                    ^       ^
                    start0  i
        """
        start0 = 0
        for i in range(len(nums)):
            if nums[i]:
                nums[i], nums[start0] = nums[start0], nums[i]
                start0 += 1

cpp

// C++ 版待补充

C++ 解法5

cpp

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        /*
        循环不变量：在循环过程中，nums 的数据分布始终如下图
        [ 非零元素 | 零元素 | 尚未遍历 ]
                    ^       ^
                    start0  i
        */
        int start0 = 0;
        for (int& x : nums) { // 注意 x 是引用
            if (x) {
                swap(x, nums[start0]);
                start0++;
            }
        }
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是 $nums$ 的长度。
空间复杂度： $O (1)$ 。

专题训练

见下面双指针题单的「§3.4 原地修改」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

方法一：把 nums 当作栈 ​

复杂度分析 ​

方法二：双指针+交换元素 ​

核心思路 ​

具体思路 ​

答疑 ​

复杂度分析 ​

专题训练 ​

分类题单 ​

方法一：把 nums 当作栈

复杂度分析

方法二：双指针+交换元素

核心思路

具体思路

答疑

复杂度分析

专题训练

分类题单