第82期-基础技巧:双指针 移动零

1 问题描述

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

示例 1:

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

示例 2:

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

初始代码

第82期-基础技巧:双指针 移动零
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 解题方法

第82期-基础技巧:双指针 移动零
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

代码运行结果为:
第82期-基础技巧:双指针 移动零

#算法讲解

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


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

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

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

 

上一篇:82. 删除排序链表中的重复元素 II


下一篇:82.删除排序链表中的重复元素Ⅱ