数组02-移除元素

Posted on

最简单暴力的移除元素就是套两层for循环 让后面的元素不断去覆盖前元素实现数组的删除

这个O(n*n)的方法大部分都是会卡掉的 我们同时也知道 双指针通常是可以优化类似的数组问题

因此我们这里就介绍一下移除数组的双指针做法

双指针的方法的核心思想你可以理解成我需要在原数组中创建一个新的数组 新的数组中不包含我们要删除的元素

那么

  • 快指针：遍历一遍整个数组，去找到符合新数组要求的元素（其实就是不等于val的元素）

  • 慢指针：指向的是新数组的最后一个下标位置 随时更新数组的内容

那么说人话就是 fast只要发现非val的值 就放在slow所在的位置

代码如下

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def removeElement(self, nums, val):
        fast=0
        slow=0
        
        while fast < len(nums):
            if nums[fast] !=val:
                nums[slow]=nums[fast]
                slow+=1
            fast+=1
        return slow