刷题记录 LeetCode HOT 100 双指针-1 移动零

题目：283. 移动零

难度：简单

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

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

示例 1:

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

示例 2:

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

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

一、模式识别：数组移动元素

数组移动元素，经典双指针问题

要求保持非零元素的相对顺序，不能用左右指针，只能用快慢指针，

用物理意义理解：

快指针runner用于遍历数组，慢指针chaser用于记录非零数字

二.代码实现

1.数字位置互换

用while循环遍历数组：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        runner = chaser = 0
        n = len(nums)
        while runner < n:
            if nums[runner] != 0:
                nums[chaser], nums[runner] = nums[runner], nums[chaser]
                chaser += 1
            runner += 1

逻辑相同，写法换成用for循环遍历数组：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        chaser = 0
        n = len(nums)
        for runner in range(n):
            if nums[runner] != 0:
                nums[runner], nums[chaser] = nums[chaser], nums[runner]
                chaser += 1

2.先赋值，后补零

不交换位置，反正把非零找全后其余数字都是零，

所以不需要交换位置，先把非零找出来，其余补0：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        chaser = 0
        for runner in range(n):
            if nums[runner] != 0:
                nums[chaser] = nums[runner]
                chaser += 1
        while chaser < n:
            nums[chaser] = 0
            chaser += 1