LeetCode简单题之移动零

题目

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
来源：力扣（LeetCode）

解题思路

此题可以用“冒泡”来解决遍历当前数组当遇到不是0的数字就将它往前“冒”，直到碰到非零数字或者左括号。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def move(i):
            while nums[i-1]==0 and i>0:  #将第i个数字(非零)前的零移动至它的后头
                temp=nums[i]
                nums[i]=nums[i-1]
                nums[i-1]=temp
                i-=1
        for i in range(len(nums)):  #逐一检查非零数字并进行移动
            if nums[i]!=0 and i!=0:
                move(i)

这样的冒泡显然是十分耗费时间的，如果数组的前端有大量的零，那么这些非零的数字恐怕是要经过长时间的“迁徙”才能到达相应的位置，这中间无疑有许多的无效移动。题目有个隐藏的属性，那就是非零数字有相对顺序，但是为零的数字顺序就变得不那么重要了，我们只需要知道非零数字它最终应该在数组中的位置即可。基于此，我们可以设置一个计数器用来记录非零数字的位置信息，当遇到一个非零数字时计数器加一，此时的计数器所示的便是当前非零数字的最终位置。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        count=-1
        num=0
        for i in nums:  #将对应的非零数字放入最终的位置
            if i!=0:
                count+=1
                nums[count]=i  
            else:
                num+=1  #统计零的个数
        if num!=0:  #在数组尾部更新为零
            nums[-num:]=num*[0]