【C语言】Leetcode 27.移除元素

一、代码实现

如果不考虑O(1)的空间复杂度的话我们可以再创建数组来进行遍历解决该问题，但是在要求之下该做法无法通过。于是我们可以用双指针来解决，最坏的情况时间复杂度为O(N)。

int removeElement(int* nums, int numsSize, int val) {
    int src = 0; // 定义源指针src，用于遍历原始数组
    int dst = 0; // 定义目标指针dst，用于指向新数组中的位置
    while(src < numsSize) { // 循环遍历源数组
        if(nums[src] != val) { // 如果源数组当前位置的值不等于目标值val
            nums[dst++] = nums[src++]; // 将当前值复制到目标数组中，并分别递增源指针和目标指针
        } else {
            ++src; // 如果源数组当前位置的值等于目标值val，则只递增源指针，不将该值复制到目标数组中
        }
    }
    return dst; // 返回新数组的长度
}

以上代码的主要思路是使用两个指针src和dst，其中src指向原始数组中的元素，而dst指向新数组中的位置。当src指向的元素不等于目标值val时，将该元素复制到新数组中，并递增dst和src指针；当src指向的元素等于目标值val时，只递增src指针，不进行复制操作。最终返回dst作为新数组的长度。

这段代码的时间复杂度为O(n)，其中n为原始数组的长度。由于只遍历一次原始数组，因此效率较高。

二、算法图解

我们设置2为val，src和dst为两个指针。

我们先让两个指针指向数组第一个元素。

由于2是val，所以src++，变成了如下。

1不是val，所以dst指向的2赋值为src所指向的元素，结果如下图。

如此类推当到了下一个val的时候再次将dst赋值给src。

最终得到的就是dst指针所指向之前的数组元素，返回的数组大小为dst。