LeetCode 27. 移除元素

2023-11-20 HGNULB 约 4 分钟

文章信息 9 个分类 2 个标签

分类

LeetCode CodeTop 简单已解决已掌握 5-10 字节跳动美团面试经典 150 题

题目描述

✅ 27. 移除元素

题意分析

输入是一个整数数组 nums 和一个目标值 val，要求把所有等于 val 的元素从数组中去掉，返回剩下的元素个数 k。

判题方式决定了这题的自由度：只检查 nums 的前 k 个位置，且这 k 个数与「原数组去掉 val 后的多重集合」相同，顺序也不做要求，k 之后的位置放什么都无所谓。也就是说，既不需要真的删除、也不需要把尾部清空，只要把该保留的元素挪到前 k 格即可。

「原地」这个词是核心约束信号：不允许另开一个数组再拷回来，额外空间必须是常数。数组无序、val 可能一个都不出现，也可能全是 val。

边界上要覆盖：空数组返回 0；所有元素都等于 val 时返回 0；没有元素等于 val 时返回原长度且数组内容不变。

解法：快慢指针覆盖

核心思路

题目只校验返回长度 k 和数组前 k 个位置，尾部内容无关。因此不必真的删除元素并反复左移，只需把应保留的元素紧凑地写回数组前部。

使用读写双指针：fast 依次读取每个元素，slow 指向下一个写入位置。读到 val 就跳过；读到其他值就写入 nums[slow]，再让 slow 加一。

循环开始处理下标 fast 时维护两个不变量：

nums[0..slow) 恰好保存原数组 nums[0..fast) 中所有不等于 val 的元素，并保持相对顺序；

slow <= fast，所以写入只会覆盖已读位置，不会破坏 nums[fast..n) 中尚未读取的数据。

跳过 val 不改变有效前缀；写入非 val 元素会把它追加到有效前缀，两种分支都保持不变量。遍历结束时 fast = n，所以 nums[0..slow) 就是全部保留元素，slow 同时等于其数量。

解题步骤

初始化 slow = 0，表示有效前缀当前为空。

用 fast 从左到右扫描数组。

若 nums[fast] == val，跳过当前元素；否则将它写到 nums[slow]，并令 slow++。

扫描完成后返回 slow，无需清理其后的数组位置。

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

fast 读到操作 slow 当前有效前缀

0 3 写入下标 0 1 [3]

1 2 跳过 1 [3]

2 2 跳过 1 [3]

3 3 写入下标 1 2 [3,3]

最终返回 2；下标 2 之后即使仍有旧值，也不属于答案。

`fast`	读到	操作	`slow`	当前有效前缀
0	3	写入下标 0	1	`[3]`
1	2	跳过	1	`[3]`
2	2	跳过	1	`[3]`
3	3	写入下标 1	2	`[3,3]`

代码实现

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

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
}

复杂度分析

时间复杂度：$O(n)$，每个元素读取一次，非 val 元素至多写入一次。

空间复杂度：$O(1)$，只使用常数个指针变量，结果直接写回原数组。

关键点总结

原地删除的本质是构造有效前缀，不是改变数组长度；返回值 k 划定了结果边界。

slow 表示已保留元素数，也表示下一个写入位置；一个变量承担两种一致的含义，可避免额外计数。

slow <= fast 是安全覆盖的关键：写指针不会越过读指针，尚未读取的数据始终完好。

该写法稳定地保留相对顺序。若顺序无关且 val 很少，可用末尾元素覆盖 val 来减少写入，但逻辑更易出错。

易错点总结

读到 val 时仍让 slow 前进：有效前缀会留下待删除元素，返回长度也会偏大。

返回 nums.length 而不是 slow：数组物理长度没有改变，只有前 slow 个位置有效。

写入后额外移动 fast：for 循环已经会更新 fast，再次递增会漏读元素。

清空 slow 之后的元素：题目明确不检查尾部，这既增加无效写入，也可能让人误以为整个数组都是结果。

首尾覆盖法中换入末尾元素后立即前进：换来的值尚未判断，连续出现 val 时容易漏删；读写指针法没有这个分支风险。

相似题目

题目	难度	考察点
26. 删除有序数组中的重复项	简单	保留条件从「不等于 `val`」变成「与前一个保留值不同」
80. 删除有序数组中的重复项 II	中等	允许重复两次，判断条件改为与 `nums[slow - 2]` 比较
283. 移动零	简单	删完还要求把零补回尾部，多一趟填充或改用交换
443. 压缩字符串	中等	写入的是「字符 + 计数」，一次可能写多格
1089. 复写零	简单	写入量大于读入量，必须从后往前倒着覆盖
75. 颜色分类	中等	三个指针同时维护三段区间，交换而非覆盖