移除元素（Remove Element）题目详解：三种解法与优化实践

题目描述

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

要求：

示例：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：函数应返回长度 2，且 nums 的前两个元素均为 2

解法一：暴力删除法（时间复杂度 O(N²)）

核心思路

遍历数组查找 val，找到后删除该位置元素，后续元素前移。

代码实现

int removeElement(int* nums, int numsSize, int val) {
int size = numsSize;
for (int i = 0; i < size; i++) {
if (nums[i] == val) { // 找到要删除的元素
// 将后续元素整体向前移动一位
for (int j = i + 1; j < size; j++) {
nums[j – 1] = nums[j];
}
i—; // 因为下标i以后的元素都向前移动了一位，所以i要减1
size—; // 数组大小减1
}
}
return size;
}

复杂度分析

• 时间复杂度：O(N²)，最坏情况下每个元素都需要移动
• 空间复杂度：O(1)，原地修改

适用场景

• 小规模数据
• 对时间复杂度要求不高的场景

解法二：辅助数组法（时间复杂度 O(N)，空间复杂度 O(N)）

核心思路

创建临时数组存储非 val 元素，再拷贝回原数组。

代码实现

int removeElement(int* nums, int numsSize, int val) {
int* tmp = (int*)malloc(sizeof(int) * numsSize); // 创建临时数组
int k = 0; // 新数组索引

// 遍历原数组，将非val元素存入临时数组
for (int i = 0; i < numsSize; i++) {
if (nums[i] != val) {
tmp[k++] = nums[i];
}
}

// 将临时数组拷贝回原数组
for (int i = 0; i < k; i++) {
nums[i] = tmp[i];
}

free(tmp); // 释放临时数组
return k;
}

复杂度分析

• 时间复杂度：O(N)，遍历两次数组
• 空间复杂度：O(N)，需要额外数组空间

适用场景

• 允许使用额外空间
• 需要保持元素原始顺序

解法三：双指针法（最优解）

核心思路

使用两个指针：

• src（源指针）：遍历原数组
• dst（目标指针）：指向下一个有效元素应该存放的位置

算法流程

可视化过程

初始：nums = [3,2,2,3], val = 3
dst=0, src=0

步骤1：nums[0]=3 == val → src=1, dst=0
步骤2：nums[1]=2 != val → nums[0]=2, dst=1, src=2
步骤3：nums[2]=2 != val → nums[1]=2, dst=2, src=3
步骤4：nums[3]=3 == val → src=4

结束：返回 dst=2, nums = [2,2,_,_]

代码实现

int removeElement(int* nums, int numsSize, int val) {
int dst = 0; // 目标指针：指向下一个有效元素位置
int src = 0; // 源指针：遍历原数组

while (src < numsSize) {
if (nums[src] != val) {
// 将有效元素移动到前面
nums[dst] = nums[src];
dst++;
}
src++; // 源指针始终向前移动
}

return dst; // dst就是新数组的长度
}

优化版本（减少赋值操作）

int removeElement(int* nums, int numsSize, int val) {
int left = 0;
int right = numsSize – 1;

while (left <= right) {
if (nums[left] == val) {
// 将val交换到数组末尾
nums[left] = nums[right];
right—;
} else {
left++;
}
}
return left;
}

复杂度分析

• 时间复杂度：O(N)，只需遍历一次数组
• 空间复杂度：O(1)，原地修改

三种解法对比

关键经验总结

1. 双指针法的核心思想

• 快慢指针：一个指针遍历，一个指针记录有效位置
• 覆盖而非删除：通过覆盖无效元素实现"删除"效果
• 原地操作：避免额外空间开销

2. 边界条件处理

• 空数组：直接返回0
• 全部元素都是val：返回0
• 没有val元素：返回原数组长度

3. 代码优化技巧

// 技巧1：简化判断逻辑
while (src < numsSize) {
if (nums[src] != val) {
nums[dst++] = nums[src]; // 合并赋值和自增
}
src++;
}

// 技巧2：使用for循环更简洁
for (int src = 0; src < numsSize; src++) {
if (nums[src] != val) {
nums[dst++] = nums[src];
}
}

4. 测试用例设计

// 测试用例1：正常情况
int nums1[] = {3,2,2,3};
assert(removeElement(nums1, 4, 3) == 2);

// 测试用例2：全部为val
int nums2[] = {1,1,1,1};
assert(removeElement(nums2, 4, 1) == 0);

// 测试用例3：没有val
int nums3[] = {4,5,6,7};
assert(removeElement(nums3, 4, 8) == 4);

// 测试用例4：空数组
assert(removeElement(NULL, 0, 5) == 0);

5. 力扣提交要点

扩展思考

1. 如果要求保持元素原始顺序？

双指针法天然保持顺序，因为是从左到右遍历和覆盖。

2. 如果val出现频率很高？

优化版本的双指针（交换法）效率更高，减少赋值次数。

3. 实际应用场景

• 内存清理：移除特定值的内存块
• 数据过滤：过滤掉无效或异常数据
• 缓存管理：淘汰特定类型的缓存项

结语

移除元素问题虽然简单，但体现了算法设计的核心思想：

掌握双指针法的思想，不仅能解决本题，还能应对：

• 删除排序数组中的重复项
• 移动零
• 合并两个有序数组
  a- 等类似问题

建议读者在理解基础上，自己手写代码实现，并尝试不同的测试用例，加深对双指针法的理解。