0027.移除元素

难度：🟢 简单

标签：数组、双指针

链接：27. 移除元素

题目描述

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

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

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

示例 1：

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

示例 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。注意这五个元素的顺序可以任意改变。

解题思路

核心思想

本题的核心是在原地修改数组，将所有不等于 val 的元素移动到数组的前面，然后返回这些元素的数量。由于题目不要求保持元素的相对顺序，这为我们提供了更多的解法选择。

思路选择

快慢指针法 是解决此问题的标准思路之一，它能保持元素的相对顺序。

• 我们使用一个“慢指针” (slow 或 writeIndex)，它指向下一个不等于 val 的元素应该被放置的位置。

• 我们使用一个“快指针” (fast 或 readIndex)，它用于遍历整个原始数组。

• 当快指针 fast 遇到一个不等于 val 的元素时，就将它“写入”到慢指针 slow 指向的位置，然后将 slow 指针后移一位。

双指针优化（首尾交换）：当需要移除的元素很少时，上面的方法会进行很多不必要的复制操作。一个更优的策略是，当我们遇到一个要移除的元素 nums[i] === val 时，直接用数组末尾的元素去覆盖它，然后缩小数组的有效范围。这种方法不会保持元素的相对顺序，但符合题目要求。

关键步骤 (快慢指针法)

1. 初始化：创建一个慢指针 slow = 0。

2. 循环遍历：用快指针 fast 从 0 开始遍历整个数组。

3. 判断与写入： a. 如果 nums[fast] 的值 不等于 val，说明这是一个需要保留的元素。 b. 将 nums[fast] 的值赋给 nums[slow]。 c. 将慢指针 slow 加一。

4. 返回结果：遍历结束后，slow 的值就是不等于 val 的元素的数量，即新数组的长度。

代码实现 (推荐)

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    // slow 指针：指向下一个应被覆盖的非 val 元素的位置
    let slow = 0;

    // fast 指针：遍历整个数组寻找非 val 元素
    for (let fast = 0; fast < nums.length; fast++) {
        // 如果当前元素不是要移除的值
        if (nums[fast] !== val) {
            // 将其移动到 slow 指针的位置
            nums[slow] = nums[fast];
            // slow 指针前进，准备下一个位置
            slow++;
        }
    }

    // slow 的值即为新数组的长度
    return slow;
};

原始代码分析 (用户提供)

您提供的代码采用的是一种首尾双指针交换的思路，逻辑是正确的，并且在某些情况下效率更高。

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function (nums, val) {
    // left 从头开始，right 从尾开始
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        // 从左边找到第一个要移除的元素
        if (nums[left] !== val) {
            left++;
            continue;
        }
        // 从右边找到第一个要保留的元素
        if (nums[right] === val) {
            right--;
            continue;
        }
        // 将右边要保留的元素换到左边要移除的位置
        nums[left] = nums[right];
        // 交换后，left 和 right 都已处理完毕，同时移动
        right--;
        left++;
    }
    // left 最终指向新数组长度的位置
    return left;
};

• 优点：此实现非常高效。当要移除的元素 val 较少时，它通过交换操作，大大减少了元素的移动次数，性能优于快慢指针法。

• 代码风格优化:

  • 逻辑上可以稍作简化。while 循环内部的 if/continue 结构可以被更紧凑的逻辑替代，但当前写法也足够清晰。

  • 您提供的代码逻辑已经是该思路的一个优秀实现，无需大的改动。

复杂度分析

• 时间复杂度：O(n) 其中 n 是数组 nums 的长度。两种双指针方法都只需要对数组进行一次完整的遍历。

• 空间复杂度：O(1) 两种方法都是在原数组上进行操作，只使用了常数个额外变量作为指针，空间消耗是恒定的。

相关题目

• 0026.删除有序数组中的重复项

• 0283.移动零

• 0080.删除有序数组中的重复项 II

总结

本题是双指针思想的经典应用。快慢指针法通用性强，能保持元素相对顺序。而首尾交换法则在不要求保持顺序的场景下，通过减少元素移动次数，可能获得更高的性能。