leetcode之移除元素

题目

给你一个数组 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循环，一个for循环遍历数组元素 ，第二个for循环更新数组。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i, l = 0, len(nums)
        while i < l:
            if nums[i] == val: # 找到等于目标值的节点
                for j in range(i+1, l): # 移除该元素，并将后面元素向前平移
                    nums[j - 1] = nums[j]
                l -= 1
                i -= 1
            i += 1
        return l

解题思路，具体的步骤如下：

1. 初始化指针 i 为 0，表示数组的开始位置，l 为数组的长度。

2. 进入一个 while 循环，条件是 i 小于 l。

3. 在每次循环中，我们检查 i 指向的元素是否等于给定值。如果等于给定值，那么我们就进入一个 for 循环，将 i 后面的所有元素向前移动一位，覆盖 i 位置的元素。然后，我们将 l 减 1，表示数组的长度减小了 1。同时，我们将 i 减 1，以便在下一次循环时重新检查这个位置的元素。

4. 如果 i 指向的元素不等于给定值，或者已经处理完等于给定值的元素，我们就将 i 加 1，移动到下一个位置。

5. 当遍历完整个数组后，l 的值就是数组中不等于给定值的元素的数量，也就是我们的答案。

快慢指针

快慢指针是一种常用的编程技巧，通常用于处理数组或链表的问题。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        # 快慢指针
        fast = 0  # 快指针
        slow = 0  # 慢指针
        size = len(nums)
        while fast < size:  # 不加等于是因为，a = size 时，nums[a] 会越界
            # slow 用来收集不等于 val 的值，如果 fast 对应值不等于 val，则把它与 slow 替换
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

解题思路：

使用快指针 fast 来遍历数组，慢指针 slow 用于指向下一个可能被替换的位置。

具体的步骤如下：

1. 初始化快慢指针为 0，表示数组的开始位置。
2. 进入一个 while 循环，条件是快指针小于数组的长度。
3. 在每次循环中，我们检查快指针指向的元素是否等于给定值。如果不等于给定值，那么我们就把这个元素复制到慢指针的位置，然后把慢指针向前移动一步。
4. 不管快指针指向的元素是否等于给定值，我们都把快指针向前移动一步。
5. 当遍历完整个数组后，慢指针的位置就是数组中不等于给定值的元素的数量，也就是我们的答案。

这个方法的优点是，它只需要遍历一次数组，时间复杂度是 O(n)，其中 n 是数组的长度。同时，它不需要额外的空间，空间复杂度是 O(1)。

动态可视化

初始列表是[3,6,5, 2, 2, 3, 4, 2]，移除2，结果返回返回移除后数组的新长度。

双重for循环

快慢指针