27.移除元素

一、问题描述

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

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例：

给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

二、方案一：双指针法

1、思路

• 使用快慢指针，快指针遍历数组，慢指针指向下一个要填充的位置。
• 当快指针指向的元素不等于 val 时，将其值复制到慢指针位置，并移动慢指针。

2、代码实现

func removeElement(nums []int, val int) int {
    slow := 0
    for fast := 0; fast < len(nums); fast++ {
        if nums[fast] != val {
            nums[slow] = nums[fast]
            slow++
        }
    }
    return slow
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。
• 空间复杂度：O(1)，只需要常数的空间。

三、方案二：交换法

1、思路

• 遍历数组，当遇到等于 val 的元素时，将其与数组末尾的元素交换，并减小数组长度。
• 注意，交换后不能立即移动指针，因为新的元素可能是 val。

2、代码实现

func removeElement(nums []int, val int) int {
    i := 0
    n := len(nums)
    for i < n {
        if nums[i] == val {
            nums[i] = nums[n-1]
            n--
        } else {
            i++
        }
    }
    return n
}

3、复杂度分析

• 时间复杂度：O(n)，最坏情况下数组中每个元素都需要交换。
• 空间复杂度：O(1)，不需要额外空间。

四、总结

方案	时间复杂度	空间复杂度	优点	缺点
双指针法	O(n)	O(1)	简洁，不需要额外空间	可能需要复制元素
交换法	O(n)	O(1)	不需要额外空间，不需要复制元素	可能需要多次交换，数组中的元素顺序可能发生变化

推荐方案：双指针法，因为其实现更简洁且容易理解。