1 问题描述

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

示例 1:

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

示例 2:

输入: [0]
输出: [0]

初始代码

from typing import List
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        #在此之间填写代码

print(Solution().moveZeroes([0,1,0,3,12]))
print(Solution().moveZeroes([0]))

View Code

2 解题思路

• 标签：双指针
• 使用双指针，快指针指向当前已经处理好的序列的尾部，慢指针指向新列表0的头部。
• 快指针不断向右移动，每次快指针指向零，则将0添加到新列表尾部
• 每次快指针指向非零数，则将该数插入新列表指针对应位置

#3 解题方法

from typing import List
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        slow,fast=0,0
        a,b=len(nums),[]
        while fast<a:
            if nums[fast]!=0:
                b.insert(slow,nums[fast])
                slow+=1
            else:
                b.append(0)
            fast+=1
        return b

print(Solution().moveZeroes([0,1,0,3,12]))
print(Solution().moveZeroes([0]))

View Code

第1-3，14-15行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑
第4行： 定义变量fast,slow分别赋值0,0，用于表示快慢指针
第5行： 定义变量a并赋值nums列表的长度，定义空列表b
第6行： 当快指针fast小于a时，执行循环
第7行： 判断快指针对应的元素是否不等于0
第8行： 若不相等，则在列表b慢指针的位置插入该元素
第9行： 慢指针进一
第10行： 若等于0，则在列表b尾部加入0
第11行： 不管是否相等，快指针都进一
第12行： 输出列表b

代码运行结果为：

#算法讲解

这里用到了基础技巧：双指针，简单讲解下这个技巧：
什么是双指针（对撞指针、快慢指针）
双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

用法
对撞指针
对撞指针是指在有序数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。

对撞数组适用于有序数组，也就是说当你遇到题目给定有序数组时，应该第一时间想到用对撞指针解题。

快慢指针
快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如fast每次增长两个，slow每次增长一个。