LeetCode 27. 移除元素（C）解题分析

题目：27. 移除元素
语言：C
分析日期：2026-10-14
代码来源：用户于 2026-10-14 在本对话中粘贴的函数（user pasted）
结论：你的代码能正确保留所有不等于 val 的元素，并保持它们的相对顺序；但它创建了 int n[numsSize]，额外空间为 O(numsSize)，不符合题目要求的 O(1) 额外空间。推荐使用单指针覆盖法。

1. 题意和输入模型

题目给出整数数组 nums 和整数 val，要求原地移除所有等于 val 的元素，并返回不等于 val 的元素数量 k。

题目只检查修改后的 nums[0..k-1]。k 之后的内容可以是任意值，不需要清零，也不需要保持原样。

项目	含义
nums[0..numsSize-1]	输入数组的全部有效元素
val	需要移除的目标值
返回值 k	保留元素的数量
结果要求	nums[0..k-1] 中不能出现 val
顺序要求	题面不强制稳定顺序；保留相对顺序是更直观的选择
额外空间	O(1)

这里必须区分两个概念：

物理数组容量：numsSize 个 int
逻辑结果区间：nums[0..k-1]
                       ↑
                  返回 k

被“移除”的元素不需要真的从内存中消失。只要把保留元素写到数组前缀，并返回前缀长度 k，就完成了题目定义的移除。

边界情况

• numsSize == 0：返回 0。

• 所有元素都等于 val：返回 0。

• 没有元素等于 val：返回 numsSize，数组可以保持不变。

• val 可以是负数、0 或正数；不能把某个数值当作空位哨兵。

• numsSize == 1：仍然可以直接处理。

2. 你的实现

int removeElement(int* nums, int numsSize, int val) {
    int n[numsSize];
    int p = 0;

    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != val) {
            n[p] = nums[i];
            p++;
        }
    }

    for (int j = 0; j < p; j++) {
        nums[j] = n[j];
    }

    return p;
}

3. 逐分支检查

3.1 正确的部分

第一轮扫描中：

if (nums[i] != val) {
    n[p] = nums[i];
    p++;
}

循环结束时，n[0..p-1] 恰好保存了所有不等于 val 的元素，且顺序与原数组一致。

第二轮：

for (int j = 0; j < p; j++) {
    nums[j] = n[j];
}

把这些保留元素复制回 nums 的前缀，因此返回 p 后，nums[0..p-1] 满足题目要求。

你的实现不会把合法的 0、负数或其他值误判为空位，也没有修改 val 或引入排序，因此在结果正确性上没有发现反例。

3.2 主要问题：额外空间违反题目约束

int n[numsSize];

这是一个 C99 变长数组（VLA），需要为最多 numsSize 个 int 分配栈空间。因此：

项目	你的实现
时间复杂度	O(numsSize)
额外空间	O(numsSize)
是否原地	结果写回 nums，但使用了线性辅助数组
题目约束	不满足 O(1) 额外空间

这不是仅影响性能的细节，而是题目明确要求的空间复杂度不合规。在线评测可能仍然接受某些测试规模下的代码，但算法分析和提交质量都应判定为不符合进阶要求。

3.3 C 语言和可移植性风险

int n[numsSize] 还有两个需要注意的 C 语言问题：

1. VLA 不是所有编译器都支持。
   VLA 从 C99 开始被标准化，但在 C11 以后属于可选特性；MSVC 的传统 C 编译器也不按 GCC/Clang 的方式支持它。若题目环境使用支持 VLA 的编译器，代码可能正常编译；作为通用 C 代码，不能假设所有编译器都接受。

2. numsSize == 0 时不能依赖零长度数组。
   题目允许空数组。int n[0] 不是标准 C 中可移植的数组声明；某些编译器会把它作为扩展接受，另一些编译器会报错或给出诊断。即使当前平台放行，也没有必要为这个边界引入风险。

如果改成 malloc，虽然能避免栈上 VLA，但额外空间仍然是 O(numsSize)，并没有满足本题的 O(1) 要求。

3.4 不必要的两阶段复制

你的代码先把保留元素写入 n，再从 n 复制回 nums。这相当于每个保留元素最多写两次。

可以直接使用 p 作为 nums 的写指针：

读取指针 i：依次查看原数组元素
写入指针 p：写入下一个保留元素

当 nums[i] == val：跳过
当 nums[i] != val：nums[p] = nums[i]，p++

由于 p 不会大于 i，写入位置不会超过当前读取位置，不会覆盖尚未读取的元素。

4. 推荐算法：双指针覆盖法

flowchart LR
    A[初始化 p = 0] --> B{扫描 i = 0 到 numsSize - 1}
    B --> C{nums[i] == val?}
    C -- 是 --> D[跳过当前元素]
    C -- 否 --> E[nums[p] = nums[i]; p++]
    D --> B
    E --> B
    B -->|扫描结束| F[返回 p]

推荐实现：

int removeElement(int* nums, int numsSize, int val) {
    int p = 0;

    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] != val) {
            nums[p] = nums[i];
            ++p;
        }
    }

    return p;
}

循环不变量和正确性证明

设循环处理到下标 i 之前：

1. nums[0..p-1] 恰好保存原数组 nums[0..i-1] 中所有不等于 val 的元素；

2. 这些元素的相对顺序保持不变；

3. 0 <= p <= i。

初始化时，i == 0、p == 0，结果前缀为空，不变量成立。

每轮处理 nums[i]：

• 若 nums[i] == val，它不应进入结果，p 不变；原有结果前缀仍正确。

• 若 nums[i] != val，将它写入 nums[p]，并令 p++。由于 p <= i，写入位置不会超过当前读取位置，尚未读取的区间不会被覆盖；结果前缀继续按原顺序扩展。

扫描结束后，nums[0..p-1] 就是原数组中所有不等于 val 的元素，返回 p 正确。

原数组： [3, 2, 2, 3]
val = 3

i = 0, nums[i] = 3  -> 跳过，p = 0
i = 1, nums[i] = 2  -> nums[0] = 2，p = 1
i = 2, nums[i] = 2  -> nums[1] = 2，p = 2
i = 3, nums[i] = 3  -> 跳过，p = 2

结果前缀： [2, 2]
返回：2

5. 复杂度比较

方案	时间复杂度	额外空间	顺序	结论
你的实现：辅助 VLA + 回写	O(numsSize)	O(numsSize)	保持	结果正确，但不满足空间约束
推荐：单指针覆盖	O(numsSize)	O(1)	保持	满足题目要求
可选：交换到末尾	O(numsSize)	O(1)	可能改变	适合不要求稳定顺序时减少写入

本题还可以利用“顺序不作要求”做一个交换优化：遇到 val 时，用数组末尾尚未处理的元素替换它，并缩短有效区间。这种做法可能减少写入次数，但控制流更复杂，也可能改变保留元素的相对顺序。对于学习和面试表达，稳定的单指针覆盖法更清晰。

6. 找到 val 后从末尾交换的可选版本

如果明确不需要保持剩余元素的相对顺序，可以使用：

int removeElement(int* nums, int numsSize, int val) {
    int k = numsSize;
    int i = 0;

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

    return k;
}

这里替换进来的元素必须重新检查，所以命中 val 时不递增 i。例如：

nums = [2, 3, 3, 2], val = 3

i = 1, k = 4
用 nums[3] = 2 替换 nums[1]，k = 3
此时 nums[1] 仍需检查，但它是 2

这段代码同样是 O(n) 时间、O(1) 空间，但稳定性较弱。若题目或后续代码依赖保留元素顺序，应使用单指针覆盖法。

7. 回归测试矩阵

下面的测试只比较返回值 k 和 nums[0..k-1]，因为题目明确允许忽略 k 之后的内容。

输入 nums	val	期望 k	期望有效前缀	覆盖点
[3,2,2,3]	3	2	[2,2]	常规示例
[0,1,2,2,3,0,4,2]	2	5	[0,1,3,0,4]	0 是合法值，重复目标值
[]	1	0	[]	空数组
[1]	1	0	[]	单元素且被移除
[1]	2	1	[1]	单元素且保留
[2,2,2]	2	0	[]	全部移除
[1,2,3]	4	3	[1,2,3]	没有目标值
[-2,-1,0,1]	-2	3	[-1,0,1]	负数目标值
[5,5,1,5,2]	5	2	[1,2]	目标值在开头、中间
[1,1,2,1,3]	1	2	[2,3]	非连续保留元素

8. 分项结论

检查项	结论	类型
保留元素判断 nums[i] != val	正确	正确性
保留元素相对顺序	正确保持	正确选择
返回保留数量 p	正确	正确性
0、负数等合法值	没有误用哨兵	正确性
int n[numsSize]	线性额外空间	题目约束问题
numsSize == 0	VLA 存在可移植性风险	C/可移植性
C 编译器支持	依赖 VLA 支持	可移植性
整数溢出	无算术运算，未发现溢出风险	安全性
时间复杂度	O(n)	合格

9. 最终建议

你的代码的筛选逻辑是正确的，但不应使用 int n[numsSize] 保存完整结果。将辅助数组去掉，让 p 直接成为 nums 内的写指针，就能在保持相对顺序的同时把额外空间降为 O(1)：

int removeElement(int* nums, int numsSize, int val) {
    int p = 0;

    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] != val) {
            nums[p++] = nums[i];
        }
    }

    return p;
}

这也是本题最值得掌握的抽象：数组题中的“删除”通常不是缩短内存，而是用写指针构造符合条件的有效前缀，并返回该前缀长度。

10. 来源与证据限制

1. LeetCode CN 27. 移除元素：题目定义、原地修改语义、返回 k 的有效前缀语义、数组长度和值域约束。公开页面访问日期：2026-10-14。

2. LeetCode CN 27. 移除元素（canonical description 路径）：用于核对题面。公开页面访问日期：2026-10-14。

本次没有读取用户的 LeetCode 编辑器或提交状态；个人代码来源仅为本对话中用户粘贴的函数。因此，本文评价的是这段源码在题目约束下的静态行为，不声称它已经在 LeetCode 提交并通过。

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/HECHENNIU/article/details/167922336