题目来源LeetCode 27.移除元素
本贴为个人日常刷题笔记，有任何问题欢迎随时交流~
该题类别是：数组

一、题目

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

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

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

二、提示

  • 0 ≤ n u m s . l e n g t h ≤ 100 0 \le nums.length \le 100 0≤nums.length≤100
  • 0 ≤ n u m s [ i ] ≤ 50 0 \le nums[i] \le 50 0≤nums[i]≤50
  • 0 ≤ v a l ≤ 100 0 \le val \le 100 0≤val≤100

三、思考

  • 边界：长度为0时，直接返回0

  • 原地移除， O ( 1 ) O(1) O(1)的额外空间

  • 返回长度

  • 数组可能无序

  • 类似于leetcode26，是否可以采用双指针？

  • 是否考虑原地排序（快速排序，平均是 O ( n l o g n ) O(nlogn) O(nlogn)）？

四、解法（快慢双指针）

  • 快慢双指针

  • 慢指针从-1开始，快指针从0开始

  • 若快指针对应的值等于val，快指针后移

  • 若快指针对应的值不等于val，慢指针后移，慢指针指向值换成快指针对应值，快指针继续后移

  • 直到快指针移动到len(nums)

  • 返回慢指针index+1

  • 时间复杂度是 O ( n ) O(n) O(n)

class Solution:
    def removeElement(self, nums, val):
        i = -1
        j = 0
        while j < len(nums):
            if nums[j] != val:
                i += 1
                nums[i] = nums[j]
            j += 1
        return i + 1