题目链接

题目描述

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

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

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

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4

你不需要考虑数组中超出新长度后面的元素

思路

快慢指针：一个快指针，一个慢指针，在一个for循环下完成，比暴力更高效

快慢指针是同向指针的一种，只是快慢指针的步长一般都是固定的

慢指针用于存放非val的元素，快指针用于跳过为val的元素

快指针遍历完即代表结束，直接递增即可

慢指针的增长只依赖于判断当前元素，题目不要求考虑不符合要求的元素部分，所以慢指针需要遇到符合条件的元素（这个需要快指针来帮忙判断）才能+1

初始化

快慢指针为同向指针，都初始化为0

循环条件

只需要观察快指针，当快指针遍历整个数组即意味着结束

当快指针等于数组长度-1的时候是可以进入循环的，因为如果最后一个元素不等于 val，那么是需要将该元素输入到nums[left]的，即慢指针仍然是有可能要利用到快指针的值的（此时快指针指向数组最后一个元素）

代码

Python

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        left = 0
        right = 0
        k = 0
        while right <= len(nums)-1:
            if nums[right] != val:
                nums[left] = nums[right]
                k+=1
                left+=1
            right+=1
        return k

复杂度分析

时间复杂度： O(n) （while单循环，单循环内都是常数时间的操作）

空间复杂度： O(1) （在原数组修改，没有其余新的数组空间产生）

易错点

  • 是在原数组进行修改，只需要返回k，不需要返回一个新数组，自己创建新数组不符合要求。
  • while的边界条件包括等号，否则如果最后一个元素符合条件（需要加入到重组后的数组的时候），会在答案里漏掉最后一个元素。

收获

  • 快慢指针的步长通常是相同的。
  • 初步学习了快慢指针的使用方法，需要继续加练。
  • 出现原地修改的关键词的时候，可以考虑双指针方法。
  • 双指针一般快指针是正常遍历，而慢指针是用于条件判断。
  • in-place代表原地修改数组