6、移动零

题目描述

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

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

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
链接：https://leetcode-cn.com/problems/move-zeroes

方法1、双指针

思路：定义两个指针，left、right都指向数组开头。用right指针去遍历所有的数，当该数!=0时，right指向的数和left指的数互换，并且left+1，保证left左边的数都不为0（即left始终指向0）。

时间复杂度：O(n)，每个数最多被遍历2次。

空间复杂度：O(1)，只需要常数的空间存放数字。（数组长度）

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

方法2、不为0的覆盖到最前面，最后补0

思路：也是两个指针，不采用一个一个移动的方法，而是把不为0的直接覆盖到前面，最后遍历完一遍，后面补0。（我觉得方法1更优雅…)

时间复杂度：同1

空间复杂度：同1

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