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

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

?前言

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

179ebb4fb8844dac87d08c4dc542f6d9.png



?正文

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

?解法一、逐个判断

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

6c68bcedf5d6462987b2ec4ebd5ee44b.gif


因为题目给的是数组,而非顺序表的常规结构,因此在设计任意删除函数时,需要多设计一个参数len ,不然就很难控制循环的终止

注意: 在实际写代码时,每删除一次元素,i 都要回退一次,因为有的测试用例是 3 3 3 3val = 3,如果不回退,直接覆盖,会少删两个元素。

//27.移除数组//思路1,一个一个判断#include<assert.h>voidErase(int*nums, intpos, intlen)
{
//因为题目给的是数组,所以我们要对顺序表的任意删做点改变//比如给出第三个参数长度assert(len>0);    //如果长度小于等于0,就报错while (pos<len-1)
    {
nums[pos] =nums[pos+1];  //用数组的方式覆盖pos++;  //下标++,向后移动    }
}
intremoveElement(int*nums, intnumsSize, intval)
{
assert(nums);   //nums不能为空指针inti=0;
intlen=numsSize;
for (i=0; i<numsSize; i++)
    {
if (nums[i] ==val)
        {
Erase(nums, i, numsSize--);
i--;    //这里要--的原因是防止漏掉val,多判断一次len--;  //总长度会-1        }
    }
returnlen; //返回的是删除后的数组长度}

?解法二、分离注入

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

b7dbb59fea3f4c1ab7f63d8ff563eebe.gif

//27.移除数组//思路2,以空间换时间#include<stdlib.h>#include<assert.h>intremoveElement(int*nums, intnumsSize, intval)
{
int*pa= (int*)malloc(sizeof(int) *numsSize); //动态申请内存assert(pa); //预防申请失败的情况inti=0;  //原数组的下标intj=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;  //指针置空returnj;   //此时新数组的下标就是有效元素数}

?解法三、双指针覆盖

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

f411b13e20c948ba9e13acb8ff53c8db.gif

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

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

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

3faed1c1a1df4fabb6a53097c1eeb6a5.gif

//27.移除数组//思路4,双指针左右交换版#include<assert.h>intremoveElement(int*nums, intnumsSize, intval)
{
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--;  //其实可以在交换后,让左右指针各走一步        }
    }
intlen=0;    //记录返回的长度inti=0;
for (i=0; i<numsSize; i++)
    {
//如果元素不等于val,长度就可以统计if (nums[i] !=val)
len++;
    }
returnlen; //返回长度}



?总结

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

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

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

c3a2fbd4cece4640b5ba77b478ae727a.jpg

目录
相关文章
|
4天前
|
C语言 开发者
C语言中如何精确实现数组元素的插入
C语言中如何精确实现数组元素的插入
|
4天前
|
算法 C语言
【C语言】Leetcode 27.移除元素
【C语言】Leetcode 27.移除元素
22 0
【C语言】Leetcode 27.移除元素
|
4天前
|
存储 算法 C语言
C语言查找数组中特定元素
C语言查找数组中特定元素
85 0
|
4天前
|
C语言
C语言写元素类
C语言写元素类
25 0
|
7月前
|
C语言
C语言之冒泡法对数组元素进行排序
C语言之冒泡法对数组元素进行排序
|
4天前
|
存储 C语言
C语言中字符串的引用与数组元素操作
C语言中字符串的引用与数组元素操作
23 0
|
4天前
|
存储 C语言 索引
引用一堆数组元素在c语言中
引用一堆数组元素在c语言中
19 0
|
4天前
|
存储 算法 C语言
快速查找C语言数组中的元素
快速查找C语言数组中的元素
|
4天前
|
存储 算法 安全
C语言:数组元素的删除
C语言:数组元素的删除
|
4天前
|
算法 程序员 C语言
普通程序员也能秒查数组中特定元素,C语言的神秘技巧揭秘!
普通程序员也能秒查数组中特定元素,C语言的神秘技巧揭秘!
17 0


http://www.vxiaotou.com