C语言实现移除元素：从暴力法到双指针最优解

问题分析与场景

在处理线性表（如数组）时，经常需要剔除其中等于某特定值 val 的元素，并返回新数组的长度。这类问题核心在于如何在保证数据正确性的前提下，平衡时间与空间资源。以下图片展示了典型的问题输入输出示例：

思路一：暴力移位法

第1步：定位目标元素并后移覆盖

目的：找到第一个等于 val 的位置，并用后续元素依次前移覆盖该位置。
原理：遍历数组，一旦发现目标值，就将该位置之后的所有元素向前移动一位。
缺陷：当数组中大部分元素均为 val 时，每个元素的移除都需要大量位移操作，导致效率低下。

// 查找函数：返回val第一次出现的索引，未找到返回-1
int find(int* nums, int numsSize, int val) {
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == val) return i;
    }
    return -1;
}

// 主处理函数
int removeElement(int* nums, int numsSize, int val) {
    int ret;
    // 循环查找并移除，直到找不到为止
    while ((ret = find(nums, numsSize, val)) != -1) {
        // 从ret位置开始，将后续元素前移覆盖
        for (int i = ret; i < numsSize - 1; i++) {
            nums[i] = nums[i + 1];
        }
        numsSize--; // 有效长度减1
    }
    return numsSize;
}

该方法虽然直观，但在最坏情况下（例如所有元素都需删除），时间复杂度趋近于 O(n^2)，执行效率较低。图片展示了这一过程中的数据流动示意：

思路二：辅助数组法

第2步：筛选非目标值并存入临时数组

目的：避免重复移位带来的性能损耗，通过开辟新空间换取线性时间复杂度。
操作：创建一个与原数组等大的临时数组 tmp，遍历原数组，仅将不等于 val 的元素存入 tmp，最后再拷贝回原数组。

int removeElement(int* nums, int numsSize, int val) {
    // 特殊处理空数组情况，防止变长数组长度为0的编译错误或运行时问题
    if (numsSize == 0) return 0;
    
    int tmp[numsSize]; // 局部变量数组作为缓冲区
    int count = 0;
    
    // 第一轮：筛选有效数据
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != val) {
            tmp[count++] = nums[i];
        }
    }
    
    // 第二轮：将结果写回原数组
    for (int i = 0; i < count; i++) {
        nums[i] = tmp[i];
    }
    
    return count;
}

此方法将时间复杂度优化至 O(n)，但代价是引入了 O(n) 的空间复杂度。图片说明了数据从源数组流向临时数组再回归的过程：

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

第3步：同步遍历与原地替换

目的：结合思路一的O(1)空间和思路二的O(n)时间，实现原地高效修改。
操作：使用两个指针 src（快指针/源指针）和 dest（慢指针/目标指针）。
- src 负责遍历整个数组寻找有效数据。
- dest 负责指向下一个有效数据应该存放的位置。
当 nums[src] 不等于 val 时，将其赋值给 nums[dest]，随后两指针同时后移；若相等，仅 src 后移，dest 保持不变以覆盖无效数据。

int removeElement(int* nums, int numsSize, int val) {
    int src = 0;   // 快指针：用于读取
    int dest = 0;  // 慢指针：用于写入
    
    while (src < numsSize) {
        if (nums[src] != val) {
            nums[dest] = nums[src]; // 将有效值覆盖到dest位置
            dest++;                 // dest位置已占用，准备下一个
        }
        src++;                    // src始终向前探索
    }
    
    return dest; // 此时dest即为新数组的有效长度
}

该方法只需遍历一次数组，时间复杂度为 O(n)，且无需额外存储空间，空间复杂度为 O(1)，是处理此类问题的最佳实践。图示如下：

总结与对比

通过对上述三种方案的拆解，我们可以清晰地看到算法优化的轨迹：暴力法虽易理解但性能受限；辅助数组法解决了速度问题却牺牲了内存；双指针法则在两者间取得了完美平衡。在实际工程或考试中，推荐优先掌握双指针逻辑，它不仅能解决“移除元素”问题，也是处理链表、字符串及排序算法（如快速排序分区）的核心技巧之一。

以上就是C语言移除元素的三种思路讲解，更多关于C语言算法优化的资料请关注本站其它相关文章！