【C】顺序表算法题 -- 移除元素
同样的，了解了顺序表的实现之后，我们就该通过算法题来巩固顺序表了，接下来我们就来一道算法题移除元素。
leetcode链接
https://leetcode.cn/problems/remove-element/description/
我们来看一下问题的描述：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
- 更改
nums数组，使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。 - 返回
k。
再来看一个示例：
示例 1：
输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
移除元素就是给你一个nums数组，和一个val值，假设数组中有k个值不是val的元素，然后你需要让前k个元素位于数组的前k个位置，然后返回k，至于除这k个元素之外的元素你是删掉啊，还是位于数组后面啊，并不重要。
再来看一下题目中给的函数以及对应参数：
int removeElement(int* nums, int numsSize, int val)nums参数就是传过来的那个数组，numsSize就是数组的长度（元素个数）， val就是要移除的值。
思路1
第一个思路容易想到，就是创建一个与nums数组一样大小的新数组，然后遍历nums数组，让nums数组中不为val的值放到新数组中，并且有一个 k 记录放的次数，最后再把新数组的值放到nums数组中，最后不要忘记释放新数组的空间就可以了。
代码实现：
int removeElement(int* nums, int numsSize, int val)
{
//开辟新数组
int* newArr = (int*)malloc(sizeof(int) * numsSize);
//开辟失败的情况，不写下面这个判断代码也可以
if (newArr == NULL)
{
perror("malloc fail！\n");
exit(1);
}
//把nums数组中不为val的值放到newArr数组中
int k = 0;
for (int i = 0;i < numsSize;i++)
{
if (nums[i] != val)
{
newArr[k++] = nums[i];
}
}
//再把newArr数组的元素放到nums数组中
for (int i = 0;i < k;i++)
{
nums[i] = newArr[i];
}
//销毁newArr数组
free(newArr);
newArr = NULL;
return k;
}思路2
第二种思路不太好想，但是代码非常简洁，且很多算法都能用到，这个方法就是双指针法，双指针算法是指我们先定义两个指针（在这里实际是整型变量，代表下标），一个src指针，一个dest指针，我们让src，dest开始都指向0，然后让dest每次++，++之后没种情况有不同的处理情况，分为以下两种：
1） nums[src] == val，直接让src++
2） nums[src] != val，那么先让nums[dest] = nums[src]，
然后dest++，src++执行过程如图所示：
通过运行流程就可以看到，执行到最后dest的值就是nums数组中不为val值的个数，所以最后返回dest就可以了。
代码实现：
int removeElement(int* nums, int numsSize, int val)
{
//定义两个变量
int dest = 0,src = 0;
//循环遍历数组
while (src < numsSize)
{
//如果nums[src] == val,src++
if (nums[src] == val)
{
src++;
}
//如果nums[src != val]
else
{
nums[dest] = nums[src];
src++;
dest++;
}
}
return dest;
}当然，这个代码可以再优化，我们可以看到不管两种情况的哪一种情况，最后都是src++，所以我们只判断nums[src] != val的情况就可以了，所以优化后的代码就变成了这样：
int removeElement(int* nums, int numsSize, int val)
{
//定义两个变量
int dest = 0,src = 0;
//循环遍历数组
while (src < numsSize)
{
//如果nums[src != val]
if (nums[src] != val)
{
nums[dest] = nums[src];
dest++;
}
src++;
}
return dest;
}对于第二种算法思想双指针法，许多题目中都可以用到，所以一定要好好理解，相信大家一定可以掌握的。
原文地址：https://blog.csdn.net/L_0907/article/details/144015794
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！