27. 移除元素

题目

力扣题目

给你一个数组 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 < k; i++) {
    assert nums[i] == expectedNums[i];
}

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

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

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

考察内容

• 快慢指针
• 原地覆盖与有效区间
• 数组长度和有效元素数量的区别
• 保持顺序与不保持顺序两种实现的取舍

解题思路

题目并不要求真正缩短 nums，只要求：

1. 将所有不等于 val 的元素放到数组前部；
2. 返回这些有效元素的数量 k；
3. 下标 [k, nums.size()) 中留下什么内容都不重要。

快慢指针：保持相对顺序

• fast 扫描数组中的每个元素；
• slow 指向下一个有效元素应该写入的位置。

当 nums[fast] != val 时，把它写到 nums[slow]，然后令 slow++；当它等于 val 时直接跳过。

循环不变量是：在每轮开始时，区间 [0, slow) 中保存了已经扫描过的所有有效元素，并且这些元素的相对顺序保持不变。

以 nums = [3,2,2,3]、val = 3 为例：

最终 slow = 2，因此返回 k = 2。

首尾指针：不保持相对顺序

题目允许元素顺序发生变化，因此遇到 val 时，也可以使用当前有效区间末尾的元素覆盖它，再缩短右边界。

这种方法在待删除元素较少时可能减少写入次数，但用末尾元素覆盖后，当前位置还没有检查，所以此时不能立即移动左指针。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

代码演示

// 快慢指针：保持剩余元素的相对顺序
int removeElement(std::vector<int>& nums, int val) {
    int slow = 0;

    for (int fast = 0; fast < static_cast<int>(nums.size()); ++fast) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
    }

    return slow;
}

// 首尾指针：不保证剩余元素的相对顺序
int removeElementSwapTail(std::vector<int>& nums, int val) {
    int left  = 0;
    int right = static_cast<int>(nums.size()); // 有效区间为 [left, right)

    while (left < right) {
        if (nums[left] == val) {
            nums[left] = nums[right - 1];
            --right;
        } else {
            ++left;
        }
    }

    return left;
}

易错点

• 误以为必须删除数组尾部元素：评测只检查前 k 个元素，后面的内容无需处理。
• 返回数组原长度：应该返回有效元素数量，即快慢指针写法中的 slow。
• 每次都调用 erase：vector::erase 会移动后续元素，反复调用可能使时间复杂度退化为 $O(n^2)$。
• 无条件执行覆盖：只有当 nums[fast] != val 时，才把元素写入有效前缀。
• 尾部覆盖后立即移动 left：换过来的元素可能仍等于 val，必须在下一轮继续检查当前位置。
• 错误理解“原地”：原地算法允许使用少量变量，但不能再创建一个与输入规模相关的新数组。

总结

快慢指针把“删除元素”转换成“保留有效元素”：fast 负责读取，slow 负责写入。处理完成后，[0, slow) 就是题目要求的有效区间。

如果需要保持剩余元素的相对顺序，使用快慢指针；如果顺序不重要并希望减少部分写入，可以用尾部元素覆盖待删除位置。两种方法的时间复杂度都是 $O(n)$，额外空间复杂度都是 $O(1)$。

相关题目

• 26. 删除有序数组中的重复项
• 80. 删除有序数组中的重复项 II
• 283. 移动零
• 844. 比较含退格的字符串
• 977. 有序数组的平方