题目描述

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

理解题意

原地修改数组，指的是直接对数组参数取下标来修改数组元素，而不是通过将数组参数引用指向一个新的数组。
返回值为与val不等的元素个数。

解法——快慢指针

解法关键词：

双指针
快慢指针
我们将算法结束后关心的前n个元素，称为压实数组。因为整个过程看起来就是在往左压实。
compactIndex代表即将加入压实数组的那个元素应该赋值的索引。所以初始时，compactIndex为0，因为初始时一个非val元素都没有得到确认。
cursor即为遍历指针。
当遍历元素非val时，将其赋值给compactIndex位置，并compactIndex增加1.
由于compactIndex刚好与压实数组的长度一样，所以函数返回compactIndex。

图中最后一步，压实数组中两个元素颜色不同，是因为它们可能不相等，但都不是val。

class Solution:

def removeElement(self, nums: List[int], val: int) -> int:
    compactIndex = 0
    for cursor in range(len(nums)):
        if nums[cursor] != val:
            nums[compactIndex] = nums[cursor]
            compactIndex += 1
    return compactIndex

解法——双端指针

解法关键词：

双指针
双端指针

题目中提到了元素的顺序可以修改，所以可以使用这种解法，时间复杂度一样。
在这里插入图片描述

之间的解法是通过一个指针来遍历数组，现在则是通过两端的指针来遍历数组，通过待确认的元素纳入两个指针的范围内。左指针往右移动，右指针往左移动。
通过left指针来判断压实数组的末尾，因为left总是指向压实数组最大索引+1。（最大索引+1 就是长度）
如果数组都是val，那么left不动，right一直移动；如果数组都非val，那么right不动，left一直移动。
当left元素非val时，说明它不是想要的，则可以被覆盖，覆盖的值则是right元素，并right指针减1。因为下一次检查还是从left检查。
当left元素为val时，说明它是想要的，确认了一个压实元素，则left指针移动。

图中可见，五个元素只循环了五次。

class Solution:

def removeElement(self, nums, val):
    left = 0
    right = len(nums)-1
    while(left <= right):
        if nums[left] == val:
            nums[left] = nums[right]
            right -= 1
        else:
            left += 1
    return left

因为right指向最大元素所在索引，所以区间是一个[left, right]的左闭右闭区间（每次循环中，待确认的元素，就在这个区间之中），所以最后一次循环肯定是left = right的情况。所以循环条件为left <= right。
在这里插入图片描述

class Solution:

def removeElement(self, nums, val):
    left = 0
    right = len(nums)
    while(left < right):
        if nums[left] == val:
            right -= 1
            nums[left] = nums[right]
        else:
            left += 1
    return left