LeetCode | 移动零 - HaoyangPing

分类：双指针

题目#

给定一个整数数组 nums，需要把数组中的所有 0 移动到末尾，同时保持非零元素原来的相对顺序。

要求必须原地修改数组，不能复制一个新数组作为答案。

示例：

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

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

讲解#

这道题的关键信号是：原地修改数组，并且要保持非零元素的相对顺序。

目标数组最终会变成：

1
所有非零数 + 所有 0

所以我们只需要关心一件事：下一个非零数应该放在哪里。

双指针正好适合这种场景。

right 从左到右扫描数组，负责找非零数；

left 表示下一个非零数应该放到的位置。

双指针只扫描一遍数组，时间复杂度是 O(n)，空间复杂度是 O(1)。

代码#

源码#

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

测试#

1
from src.python._283_Move_Zeroes import Solution
2

3

4
sol = Solution()
5

6
nums = [0, 1, 0, 3, 12]
7
assert sol.moveZeroes(nums) is None
8
assert nums == [1, 3, 12, 0, 0]
9

10
nums = [0]
11
sol.moveZeroes(nums)
12
assert nums == [0]
13

14
nums = [1, 0, 1]
15
sol.moveZeroes(nums)
16
assert nums == [1, 1, 0]
17

18
print("PASS")

参考资料#

LeetCode 原题：https://leetcode.com/problems/move-zeroes/
力扣官方题解：https://leetcode.cn/problems/move-zeroes/solutions/489622/yi-dong-ling-by-leetcode-solution/

音乐

音乐

题目#

讲解#

代码#

源码#

测试#

参考资料#

文章分享

评论区

音乐

文章目录