本文讲述了python基础编程100例：第81期-基础技巧：双指针 移除元素！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

第81期-基础技巧：双指针 移除元素

1 问题描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

输入: nums = [3,2,2,3], val = 3

输出: 2, nums = [2,2]

解释: 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2:

输入: nums = [0,1,2,2,3,0,4,2], val = 2

输出: 5, nums = [0,1,4,0,3]

解释: 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

初始代码

from typing import List

class Solution:

    def removeElement(self, nums: List[int], val: int) -> int:

        #在此之间填写代码

print(Solution().removeElement([3,2,2,3],3))

print(Solution().removeElement([0,1,2,2,3,0,4,2],2))

2 解题思路

标签：双指针

由于题目要求删除数组中等于 val 的元素，因此输出数组的长度一定小于等于输入数组的长度，我们可以把输出的数组直接写在输入数组上。

可以使用双指针：右指针 right 指向当前将要处理的元素，左指针 left 指向下一个将要赋值的位置。

如果右指针指向的元素不等于 val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；

如果右指针指向的元素等于 val，它不能在输出数组里，此时左指针不动，右指针右移一位。

3 解题方法

from typing import List

class Solution:

    def removeElement(self, nums: List[int], val: int) -> int:

        slow,fast=0,0

        a=len(nums)

        while fast<a:

            if nums[fast]!=val:

                nums[slow]=nums[fast]

                slow+=1

            fast+=1

        print(nums[:slow])

        return slow

print(Solution().removeElement([3,2,2,3],3))

print(Solution().removeElement([0,1,2,2,3,0,4,2],2))

第1-3，14-15行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑

第4行： 定义慢快指针slow、fast分别赋值0，0，用于表示快慢指针

第5行： 定义变量a并赋值nums列表的长度

第6行： 当快指针fast小于a时，执行循环

第7行： 判断快指针对应的元素是否与题目给的数字相等

第8-9行： 若不相等，则令慢指针对应的元素等于快指针对应的元素

第10行： 慢指针进一

第11行： 不管是否相等，快指针都进一

第12行： 输出列表慢指针改变过的那一段列表

第13行： 输出改变过的列表长度

代码运行结果为：

算法讲解

这里用到了基础技巧：双指针，简单讲解下这个技巧：

什么是双指针（对撞指针、快慢指针）

双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

用法

对撞指针

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

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

快慢指针

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

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

如果你想用Python开辟副业赚钱，但不熟悉爬虫与反爬虫技术，没有接单途径，也缺乏兼职经验
关注下方微信公众号：Python编程学习圈，获取价值999元全套Python入门到进阶的学习资料以及教程，还有Python技术交流群一起交流学习哦。