跳至主要內容

0027. 移除元素

ITCharge大约 2 分钟

0027. 移除元素open in new window

  • 标签:数组、双指针
  • 难度:简单

题目链接

题目大意

描述:给定一个数组 numsnums,和一个值 valval

要求:不使用额外数组空间,将数组中所有数值等于 valval 值的元素移除掉,并且返回新数组的长度。

说明

  • 0nums.length1000 \le nums.length \le 100
  • 0nums[i]500 \le nums[i] \le 50
  • 0val1000 \le val \le 100

示例

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

解题思路

思路 1:快慢指针

  1. 使用两个指针 slowslowfastfastslowslow 指向处理好的非 valval 值元素数组的尾部,fastfast 指针指向当前待处理元素。
  2. 不断向右移动 fastfast 指针,每次移动到非 valval 值的元素,则将左右指针对应的数交换,交换同时将 slowslow 右移。
  3. 这样就将非 valval 值的元素进行前移,slowslow 指针左边均为处理好的非 valval 值元素,而从 slowslow 指针指向的位置开始, fastfast 指针左边都为 $val $值。
  4. 遍历结束之后,则所有 valval 值元素都移动到了右侧,且保持了非零数的相对位置。此时 slowslow 就是新数组的长度。

思路 1:代码

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow = 0
        fast = 0
        while fast < len(nums):
            if nums[fast] != val:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1
            fast += 1
        return slow

思路 1:复杂度分析

  • 时间复杂度O(n)O(n)
  • 空间复杂度O(1)O(1)