algorithms►leetcode

027-移除元素(反向遍历or双指针)

移除元素

给你一个数组 nums* 和一个值 val，你需要 原地 移除所有数值等于 val *的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    const len = nums.length;
    let count = len;
    for(let i=len; i>=0; i--) {
        if(nums[i] === val) {
            nums.splice(i, 1);
            nums.push('_')
            count--;
        }
    }
    return count;
};

注意点（反向遍历，如果用splice(index, 1)）

关键问题：当连续出现多个 val 时，正向遍历会因为 splice() 修改数组长度和索引导致漏删。以下是详细分析和修正方案：

问题分析

代码可能的缺陷

1
2
3
4
5
6
7
for(let i=0; i<len; i++) {
    if(nums[i] === val) {
        nums.splice(i, 1); // 删除后，后续元素会前移
        nums.push('_');
        count--;
    }
}
  • Bug 场景：若 nums = [3, 2, 2, 3], val = 2：
    1. 当 i=1 时，删除 nums[1]=2 → 数组变为 [3, 2, 3, '_']
    2. 下一轮 i=2，此时 nums[2]=3，漏掉了前移的 2。

根本原因

  • splice() 会改变原数组长度和索引，但循环仍按原长度 len 执行。
  • 删除元素后未调整索引 i，导致跳过后续元素检查。

其他方案

双指针（更高效）

1
2
3
4
5
6
7
8
9
10
11
12
var removeElement = function(nums, val) {
    let left = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] !== val) {
            nums[left] = nums[right];
            left++;
        }
    }
    // 可选：补位 '_'
    while (left < nums.length) nums[left++] = '_';
    return left;
};

优点：一次遍历完成删除和补位。

双指针解法图解（LeetCode 27. 移除元素）

双指针法核心思想

  • 快指针（right）：遍历原数组，寻找保留元素。
  • 慢指针（left）：指向下一个保留元素的存放位置。

双指针图解示例

输入：nums = [3, 2, 2, 3], val = 2
输出：[3, 3, _, _]（新长度为 2）

步骤 1：初始化指针

nums = [3, 2, 2, 3]
       ↑ ↑
       l r (left=0, right=0)

步骤 2：right=0，nums[0]=3 ≠ val

  • 保留 nums[0]，复制到 nums[left]。

  • left 和 right 同时右移：

    nums = [3, 2, 2, 3] (未修改)
    ↑ ↑
    l r (left=1, right=1)

步骤 3：right=1，nums[1]=2 == val

  • 跳过不保留，仅 right 右移：

    nums = [3, 2, 2, 3]
    ↑ ↑
    l r (left=1, right=2)

步骤 4：right=2，nums[2]=2 == val

  • 跳过不保留，仅 right 右移：

    nums = [3, 2, 2, 3]
    ↑ ↑
    l r (left=1, right=3)

步骤 5：right=3，nums[3]=3 ≠ val

  • 保留 nums[3]，复制到 nums[left]。

  • left 和 right 同时右移：

    nums = [3, 3, 2, 3] (left=2, right=4)
    ↑ ↑
    l r

循环结束

  • right 越界，终止循环。
  • 新长度：left = 2（前 left 个元素为有效结果）。

可选补位

1
2
3
for (let i = left; i < nums.length; i++) {
    nums[i] = '_'; // 补位
}

最终数组：

nums = [3, 3, '_', '_']

关键点总结

  1. **快指针 right**：无脑向前扫描，检查每个元素。
  2. **慢指针 left**：只接收不等于 val 的元素。
  3. 补位：在返回新长度后，将剩余位置填充 _（按题目需求）。

这种方法保证了 O(n) 时间和 O(1) 空间，是最优解。