第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。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

初始代码

第81期-基础技巧:双指针 移除元素
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))
View Code

2 解题思路

  • 标签:双指针
  • 由于题目要求删除数组中等于 val 的元素,因此输出数组的长度一定小于等于输入数组的长度,我们可以把输出的数组直接写在输入数组上。
  • 可以使用双指针:右指针 right 指向当前将要处理的元素,左指针 left 指向下一个将要赋值的位置。
  • 如果右指针指向的元素不等于 val,它一定是输出数组的一个元素,我们就将右指针指向的元素复制到左指针位置,然后将左右指针同时右移;
  • 如果右指针指向的元素等于 val,它不能在输出数组里,此时左指针不动,右指针右移一位。

#3 解题方法

第81期-基础技巧:双指针 移除元素
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))
View Code

第1-3,14-15行: 题目中已经给出的信息,运行代码时要根据这些代码进行编辑
第4行: 定义慢快指针slow、fast分别赋值0,0,用于表示快慢指针
第5行: 定义变量a并赋值nums列表的长度
第6行: 当快指针fast小于a时,执行循环
第7行: 判断快指针对应的元素是否与题目给的数字相等
第8-9行: 若不相等,则令慢指针对应的元素等于快指针对应的元素
第10行: 慢指针进一
第11行: 不管是否相等,快指针都进一
第12行: 输出列表慢指针改变过的那一段列表
第13行: 输出改变过的列表长度

代码运行结果为:
第81期-基础技巧:双指针 移除元素

#算法讲解

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


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

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

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

 

上一篇:每日一题-81(广告效果)


下一篇:windows Server 2012修复(CVE-2016-2183)(CVE-2013-2566)(CVE-2015-2808)