C语言题解 | 移除元素(多种解法)

…

🌳🌲🌱本文已收录至：C语言题解系列
更多知识尽在此专栏中！

---

---

🍉前言

这是力扣上的一道简单题，需求是 移除数组中的指定元素，并且要求 空间复杂度为O(1) ，即原地移除，我们可以用顺序表中的任意位置删除的思想解决这个题，符合题目要求，当然还有其他解法。

---

🍉正文

首先要想清楚移除的本质并不是真删除，而是把元素覆盖即可，覆盖n个元素后，数组总长度就要-n

🍍解法一、逐个判断

解法一是比较容易想到的解法，比较朴素，具体实现起来就是 从头开始遍历，找到目标元素val，就执行一次任意位置删除

因为题目给的是数组，而非顺序表的常规结构，因此在设计任意删除函数时，需要多设计一个参数len ，不然就很难控制循环的终止
注意： 在实际写代码时，每删除一次元素，i 都要回退一次，因为有的测试用例是 3 3 3 3，val = 3，如果不回退，直接覆盖，会少删两个元素。

//27.移除数组
//思路1，一个一个判断
#include
void Erase(int* nums, int pos, int len)
{
    //因为题目给的是数组，所以我们要对顺序表的任意删做点改变
    //比如给出第三个参数长度
    assert(len > 0);    //如果长度小于等于0，就报错
    while (pos < len - 1)
    {
        nums[pos] = nums[pos + 1];  //用数组的方式覆盖
        pos++;  //下标++，向后移动
    }
}

int removeElement(int* nums, int numsSize, int val)
{
    assert(nums);   //nums不能为空指针
    int i = 0;
    int len = numsSize;
    for (i = 0; i < numsSize; i++)
    {
        if (nums[i] == val)
        {
            Erase(nums, i, numsSize--);
            i--;    //这里要--的原因是防止漏掉val，多判断一次
            len--;  //总长度会-1
        }
    }

    return len; //返回的是删除后的数组长度
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

🍍解法二、分离注入

这个解法也比较容易想到，就是 创建一个额外的 数组 ，对 原数组 进行 遍历判断 ，如果元素不等于 val ，就可以放入 新数组 中，遍历 结束后，需要把 新数组 中的元素注入 原数组 中，最后再返回 新数组 的 下标 就行了。 这种方法也是比较通俗易懂，但不符合题目要求，因为我们这个开辟了 n 大小的空间，实际提交时，力扣也没说不对，可能是它无法检查得这么细吧，这个不太好的解法我也会分享给大家，但不推荐使用，可以作为一种新思路学习。

//27.移除数组
//思路2，以空间换时间
#include
#include
int removeElement(int* nums, int numsSize, int val)
{
    int* pa = (int*)malloc(sizeof(int) * numsSize); //动态申请内存
    assert(pa); //预防申请失败的情况
    int i = 0;  //原数组的下标
    int j = 0;  //新数组的下标
    for (i = 0; i < numsSize; i++)
    {
        //如果不是目标值，就将其放入到新数组中
        if (nums[i] != val)
            pa[j++] = nums[i];  //vs中会报一个小警告，原因pa[j]可能会越界，可不管
    }
    //将新数组中的元素注入到原数组中
    for (i = 0; i < j; i++)
        nums[i] = pa[i];

    free(pa);   //释放空间
    pa = NULL;  //指针置空
    return j;   //此时新数组的下标就是有效元素数
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

🍍解法三、双指针覆盖

这是一种比较巧妙的解法，用到了 双指针 ，对数组内元素进行覆盖，具体实现为：存在两个指针p1 、p2 ，两者初始都指向数组起始位置，遍历 整个数组，对指针 p1 和指针 p2 所指向的值进行比较，如果 *p1 != val ，就把 *p1 赋给 *p2 ，然后 p2 向后移动，当然无论相等还是不相等，p1 都需要往后移动，这个解法的目的就是把数组中所有非目标值的元素往前移动，最后返回 p2 - nums 的值( 两指针相减，得到的是其中间的元素个数 )

//27.移除数组
//思路3，双指针覆盖
#include
int removeElement(int* nums, int numsSize, int val)
{
    assert(nums);   //断言，防止空指针
    int* p1 = nums; 
    int* p2 = nums; //这是两个指针
    //注：直接使用numsSize没事，因为这是局部变量
    while (numsSize--)
    {
        //如果 *p1 != val，就将当前元素向前覆盖
        if (*p1 != val)
            *p2++ = *p1;    //覆盖后，p2要++
        p1++;   //p1需要一直向后移动
    }

    return p2 - nums;   //指针-指针，得到两者间的个数
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

🍍解法四、双指针左右交换

这种解法也用到了 双指针 ，不过是左右两个 指针 ，左指针 pleft 向右移动，右指针 pright 向左移动，其中，左指针 的目标是找到 val ，而 右指针 的目标是找到非 val 的元素，两者交换，显然这需要在一个大循环内嵌套两个小循环，结束条件很讲究 ，大循环为 pleft < pright，第一个小循环为 *pleft != val && pleft < pright，第二个小循环为 *pright == val && pright > pleft，这种解法速度很快，但有一个小缺陷：交换结束后，需要遍历一遍数组，确认其中的非目标元素数，并返回此值。

//27.移除数组
//思路4，双指针左右交换版
#include
int removeElement(int* nums, int numsSize, int val)
{
    assert(nums);   //断言，防止空指针
    int* pleft = nums;  //左指针，从数组起始位置开始
    int* pright = nums + numsSize - 1;  //右指针，从数组尾元素位置开始
    while (pleft < pright)
    {
        while (*pleft != val && pleft < pright)
        {
            pleft++;    //左指针向右走
        };
        while (*pright == val && pright > pleft)
        {
            pright--;   //右指针向左走
        };
        if (pleft < pright)
        {
            *pleft ^= *pright;  //因为都是整型元素
            *pright ^= *pleft;  //所以可以用异或交换法
            *pleft++ ^= *pright--;  //其实可以在交换后，让左右指针各走一步
        }
    }
    int len = 0;    //记录返回的长度
    int i = 0;
    for (i = 0; i < numsSize; i++)
    {
        //如果元素不等于val，长度就可以统计
        if (nums[i] != val)
            len++;
    }
    return len; //返回长度
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

---

🍉总结

以上就是今天给大家带来的题解文章，关于 顺序表(数组) 的题还是比较简单的，想清楚思路就行了，关于 顺序表 的OJ还有两题，后面会分享的。这是我第二次做动图，相比于之前，容易了很多，QQ录屏画质有压缩，等后面找到合适的录屏软件后，动图会更加高清 ，当然 内容也会更加扎实 ，制作动图不易，还请各位多多支持!

如果你觉得本文写的还不错的话，期待留下一个小小的赞👍，你的支持是我分享的最大动力！

如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正

…

相关文章推荐
消失的数字&轮转数组
除自身以外数组的乘积
数据结构 | 顺序表