题目描述

[EN | CN]

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

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

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

示例 1:

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

示例 2:

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

解法 1:逆序遍历

按照逆序遍历即可,遇到数值等于 val 的就删除。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(1)$,常数空间。

实现与结果如下:

1
2
3
4
5
6
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] == val:
                nums.pop(i)
        return len(nums)
  • 执行用时:44 ms,在所有 Python3 提交中击败了 43.60% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 7.14% 的用户。

解法 2:两指针遍历交换

考虑到对 listpop 操作可能带来不必要的代价(题目中不要求删除掉数组元素),因此我们将数值等于 val 的元素移动到数组最后即可(通过元素交换)。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(1)$,常数空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i, j = 0, len(nums) - 1
        while i <= j:
            if nums[i] == val:
                nums[i] = nums[j]
                j -= 1
            else:
                i += 1
        return j + 1
  • 执行用时:36 ms,在所有 Python3 提交中击败了 83.32% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 7.14% 的用户。