题目

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

示例:

1
2
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

  1. 必须在原数组上操作，不能拷贝额外的数组。
  2. 尽量减少操作次数。

题解

参照 LeetCode 官方题解，语言改为Python3

算法

  • 设置一个slow代表慢指针。
  • 用快指针遍历nums。
  • 当快指针找到一个非0数后，交换快慢指针的数。

即，快指针从前向后寻找非0数，慢指针所在的数是要被修改的数。

代码

1
2
3
4
5
6
7
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1

复杂度分析

  • 时间复杂度：O(n)O(n)。

    但是，操作是最优的。代码执行的总操作（数组写入）是非 0 元素的数量.

  • 空间复杂度：O(1)O(1)，

    只使用了常量空间。