27.移除元素

https://leetcode.cn/problems/remove-element

题目

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

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

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

示例 1:

输入: nums = [3,2,2,3], val = 3     
输出: 2       
解释: 函数应该返回新的长度 2，并且 nums 中的前两个元素均为 2。不需要考虑数组中超出新长度后面的元素。

示例 2:

输入: nums = [0,1,2,2,3,0,4,2], val = 2     
输出: 5        
解释: 函数应该返回新的长度 5，并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

思路

1. 定义慢指针 slow（初始为 0），用于记录新数组的末尾位置（最终指向新数组最后一个元素的下一位）；
2. 定义快指针 fast 遍历整个原数组，筛选出不等于 val 的元素；
3. 遍历过程中：
   • 若 nums[fast] != val，说明该元素是新数组需要保留的，将其赋值给 nums[slow]，然后 slow 后移一位；
   • 若 nums[fast] == val，跳过该元素（快指针继续前进，慢指针不动）；
4. 遍历结束后，slow 的值即为移除目标值后数组的新长度。

解法

nums = [0,1,2,2,3,0,4,2]
val = 2

def removeElement(nums, val):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
    return slow

new_length = removeElement(nums, val)
print(f"新长度: {new_length}, 数组前{new_length}个元素: {nums[:new_length]}")

解释

进阶

如果要求“移除元素后保持剩余元素的相对顺序不变”，上述解法是否依然适用？

• 适用。因为快指针是按顺序遍历原数组，有效元素会按原顺序被赋值到慢指针位置，天然保证剩余元素的相对顺序不变；
• 若想进一步优化（减少赋值操作），可改用“首尾双指针”：左指针找等于 val 的元素，右指针找不等于 val 的元素，交换两者位置，直到左右指针相遇。该方法可能改变元素顺序，但赋值次数更少。