🍉前言
这是力扣上的一道简单题,需求是 移除数组中的指定元素
,并且要求 空间复杂度为O(1)
,即原地移除,我们可以用顺序表中的任意位置删除的思想解决这个题,符合题目要求,当然还有其他解法。
🍉正文
首先要想清楚移除的本质并不是真删除,而是把元素覆盖即可,覆盖n个元素后,数组总长度就要-n
🍍解法一、逐个判断
解法一是比较容易想到的解法,比较朴素,具体实现起来就是 从头开始遍历,找到目标元素val,就执行一次任意位置删除
因为题目给的是数组,而非顺序表的常规结构,因此在设计任意删除函数时,需要多设计一个参数len
,不然就很难控制循环的终止
注意: 在实际写代码时,每删除一次元素,i
都要回退一次,因为有的测试用例是 3 3 3 3
,val = 3
,如果不回退,直接覆盖,会少删两个元素。
//27.移除数组//思路1,一个一个判断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
大小的空间,实际提交时,力扣也没说不对,可能是它无法检查得这么细吧,这个不太好的解法我也会分享给大家,但不推荐使用,可以作为一种新思路学习。
//27.移除数组//思路2,以空间换时间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
的值( 两指针相减,得到的是其中间的元素个数 )
//27.移除数组//思路3,双指针覆盖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
,这种解法速度很快,但有一个小缺陷:交换结束后,需要遍历一遍数组,确认其中的非目标元素数,并返回此值。
//27.移除数组//思路4,双指针左右交换版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录屏画质有压缩,等后面找到合适的录屏软件后,动图会更加高清 ,当然 内容也会更加扎实 ,制作动图不易,还请各位多多支持!
如果你觉得本文写的还不错的话,期待留下一个小小的赞👍,你的支持是我分享的最大动力!
如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正