283. 移动零#

题目描述#

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

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

示例 1：

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

示例 2：

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

提示：

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

解题思路#

核心思想#

双指针将所有非零元素”左倾”到数组头部，剩下的位置自然就是零。

算法步骤#

用 left 指针指向下一个应存放非零元素的位置（初始为 0）。
用 right 指针从左到右扫描整个数组。
当 nums[right] != 0 时，把 nums[right] 与 nums[left] 交换，然后 left 右移。

经过一轮扫描后，所有非零元素都被换到了 [0, left) 区间，且相对顺序不变；它们各自原来的位置留下的是 0（或左移前被换过来的 0），因此所有 0 都到了末尾。

逐步举例#

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

right	nums[right]	操作	nums 序列	left
0	0	跳过	[0,1,0,3,12]	0
1	1	交换 nums[0]<->nums[1]	[1,0,0,3,12]	1
2	0	跳过	[1,0,0,3,12]	1
3	3	交换 nums[1]<->nums[3]	[1,3,0,0,12]	2
4	12	交换 nums[2]<->nums[4]	[1,3,12,0,0]	3

最终得到 [1,3,12,0,0]，与预期一致。

复杂度分析#

时间复杂度：O(n)，只需一次遍历。
空间复杂度：O(1)，原地交换。

代码实现#

1
from typing import List
2

3

4
class Solution:
5
    def moveZeroes(self, nums: List[int]) -> None:
6
        left = 0
7
        for right in range(len(nums)):
8
            if nums[right] != 0:
9
                nums[left], nums[right] = nums[right], nums[left]
10
                left += 1

1
import sys
2
import unittest
3
from pathlib import Path
4

5
sys.path.insert(0, str(Path(__file__).parent))
6

7
from solution import Solution
8

9

10
class TestSolution(unittest.TestCase):
11
    def test_basic(self):
12
        nums = [0, 1, 0, 3, 12]
13
        Solution().moveZeroes(nums)
14
        self.assertEqual(nums, [1, 3, 12, 0, 0])
15

16
    def test_all_zero(self):
17
        nums = [0, 0, 0]
18
        Solution().moveZeroes(nums)
19
        self.assertEqual(nums, [0, 0, 0])
20

21
    def test_leading_zeros(self):
22
        nums = [0, 0, 1]
23
        Solution().moveZeroes(nums)
24
        self.assertEqual(nums, [1, 0, 0])
25

26
    def test_single(self):
27
        nums = [0]
28
        Solution().moveZeroes(nums)
29
        self.assertEqual(nums, [0])
30

31

32
if __name__ == "__main__":
33
    unittest.main()