跳到主要内容

LeetCode 27. 移除元素

本节目标

用读写双指针原地保留非目标元素，并返回有效前缀长度。

这是双指针解题框架的起点：读指针负责看完每个输入元素，写指针只记录应保留的元素。

查看原题

题意与约束​

原地移除所有等于 val 的元素，返回剩余元素个数 k。评测只检查 nums[0..k) 的多重集合，k 之后的内容不作要求。

推导与不变量​

若每次删除都搬动后面的元素，会重复移动大量内容。改为从左到右读取：进入一轮前，nums[0..write) 恰好保存已读取且不等于 val 的元素；当前 read 及其之后尚未处理。遇到应保留的值就覆盖写入 nums[write] 并后移 write，否则只继续读取。

原地修改​

函数返回值是有效前缀长度 k。只有 nums[0..k) 是移除后的结果；算法在原数组上覆盖写入，额外空间为常数。

代码实现​

两份源码都让 read 扫描数组，让 write 只在保留元素时后移。页面展示的就是行为测试实际调用的源码。

C++17
#include <vector>

using namespace std;

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int write = 0;
        for (int read = 0; read < static_cast<int>(nums.size()); read++) {
            if (nums[read] != val) {
                nums[write] = nums[read];
                write++;
            }
        }
        return write;
    }
};

复杂度分析​

  • 时间复杂度：O(n)，每个元素读取一次。
  • 空间复杂度：O(1)，只使用两个下标。

易错点​

  • 返回数组长度而不是 write，会把未定义的尾部也算进结果。
  • 遇到目标值时移动 write，会在有效前缀中留下应删除的元素。

模式迁移​

当保留条件变为“与上一个保留值不同”时，得到删除有序数组中的重复项；当还要维持非零元素相对顺序时，得到移动零。