输入#

整数数组 nums

输出#

无返回值，原地修改 nums

约束条件#

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

示例1#

1
input: nums = [0,1,0,3,12]
2
output: [1,3,12,0,0]

示例2#

1
input: nums = [0]
2
output: [0]

从直观做法出发#

最容易想到的是：先统计 0 的个数，再把非零元素按顺序填到前面，最后把剩余位置全部填 0。思路没问题，但通常需要额外数组或两次遍历，不够简洁。

另一种想法是：从左到右扫描，每遇到一个非零元素，就把它「写」到当前应该存放的位置。非零元素按扫描顺序依次写入，空出来的位置自然就是 0 了——这正是双指针能做的事。

双指针：一个扫描，一个写入#

用两个指针 i 和 j，初始都为 0：

• i：从左到右扫描整个数组
• j：指向下一个非零元素应该写入的位置

遍历过程中，若 nums[i] 非零，就把它交换到 nums[j]，然后 j 加一；若 nums[i] 为零，则什么都不做，继续让 i 往后走。

以 nums = [0, 1, 0, 3, 12] 为例：

遍历结束后，j 之后的元素本来就是 0 或被交换过来的 0，上表最后一行即为最终结果。

当 i == j 时交换等于没交换，因此非零元素在「前面没有零」的情况下不会被多余地移动，相对顺序也始终得以保持。

复杂度#

• 时间复杂度：$O(n)$，只遍历数组一次
• 空间复杂度：$O(1)$，仅使用常数额外空间

代码#

1
class Solution:
2
    def moveZeroes(self, nums: List[int]) -> None:
3
        """
4
        Do not return anything, modify nums in-place instead.
5
        """
6
        i = j = 0
7
        for i in range(len(nums)):
8
            if nums[i]:
9
                nums[i], nums[j] = nums[j], nums[i]
10
                j += 1