这是力扣上的一道简单题,需求是 移除数组中的指定元素
,并且要求 空间复杂度为O(1)
,即原地移除,我们可以用顺序表中的任意位置删除的思想解决这个题,符合题目要求,当然还有其他解法。
首先要想清楚移除的本质并不是真删除,而是把元素覆盖即可,覆盖n个元素后,数组总长度就要-n
解法一是比较容易想到的解法,比较朴素,具体实现起来就是 从头开始遍历,找到目标元素val,就执行一次任意位置删除
因为题目给的是数组,而非顺序表的常规结构,因此在设计任意删除函数时,需要多设计一个参数len
,不然就很难控制循环的终止
注意: 在实际写代码时,每删除一次元素,i
都要回退一次,因为有的测试用例是 3 3 3 3
,val = 3
,如果不回退,直接覆盖,会少删两个元素。
//27.移除数组
//思路1,一个一个判断
#include<assert.h>
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; //返回的是删除后的数组长度
}
这个解法也比较容易想到,就是 创建一个额外的 数组
,对 原数组
进行 遍历判断
,如果元素不等于 val
,就可以放入 新数组
中,遍历
结束后,需要把 新数组
中的元素注入 原数组
中,最后再返回 新数组
的 下标
就行了。 这种方法也是比较通俗易懂,但不符合题目要求,因为我们这个开辟了 n
大小的空间,实际提交时,力扣也没说不对,可能是它无法检查得这么细吧,这个不太好的解法我也会分享给大家,但不推荐使用,可以作为一种新思路学习。
//27.移除数组
//思路2,以空间换时间
#include<stdlib.h>
#include<assert.h>
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; //此时新数组的下标就是有效元素数
}
这是一种比较巧妙的解法,用到了 双指针
,对数组内元素进行覆盖,具体实现为:存在两个指针p1
、p2
,两者初始都指向数组起始位置,遍历
整个数组,对指针 p1
和指针 p2
所指向的值进行比较,如果 *p1 != val
,就把 *p1
赋给 *p2
,然后 p2
向后移动,当然无论相等还是不相等,p1
都需要往后移动,这个解法的目的就是把数组中所有非目标值的元素往前移动,最后返回 p2 - nums
的值( 两指针相减,得到的是其中间的元素个数 )
//27.移除数组
//思路3,双指针覆盖
#include<assert.h>
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; //指针-指针,得到两者间的个数
}
这种解法也用到了 双指针
,不过是左右两个 指针
,左指针 pleft
向右移动,右指针 pright
向左移动,其中,左指针
的目标是找到 val
,而 右指针
的目标是找到非 val
的元素,两者交换,显然这需要在一个大循环内嵌套两个小循环,结束条件很讲究 ,大循环为 pleft < pright
,第一个小循环为 *pleft != val && pleft < pright
,第二个小循环为 *pright == val && pright > pleft
,这种解法速度很快,但有一个小缺陷:交换结束后,需要遍历一遍数组,确认其中的非目标元素数,并返回此值。
//27.移除数组
//思路4,双指针左右交换版
#include<assert.h>
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; //返回长度
}
以上就是今天给大家带来的题解文章,关于 顺序表(数组)
的题还是比较简单的,想清楚思路就行了,关于 顺序表
的OJ还有两题,后面会分享的。这是我第二次做动图,相比于之前,容易了很多,QQ录屏画质有压缩,等后面找到合适的录屏软件后,动图会更加高清
,当然 内容也会更加扎实
,制作动图不易,还请各位多多支持!