【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个元素之外的元素你是删掉啊，还是位于数组后面啊，并不紧张。
  再来看一下标题中给的函数以及对应参数：

1. int removeElement(int* nums, int numsSize, int val)

复制代码

nums参数就是传过来的那个数组，numsSize就是数组的长度（元素个数）， val就是要移除的值。
思路1

  第一个思路轻易想到，就是创建一个与nums数组一样巨细的新数组，然后遍历nums数组，让nums数组中不为val的值放到新数组中，而且有一个 k 纪录放的次数，末了再把新数组的值放到nums数组中，末了不要忘记释放新数组的空间就可以了。
  代码实现：

1. int removeElement(int* nums, int numsSize, int val)
2. {
3.   //开辟新数组
4.   int* newArr = (int*)malloc(sizeof(int) * numsSize);
5.   //开辟失败的情况，不写下面这个判断代码也可以
6.   if (newArr == NULL)
7.   {
8.     perror("malloc fail！\n");
9.     exit(1);
10.   }
11.   //把nums数组中不为val的值放到newArr数组中
12.   int k = 0;
13.   for (int i = 0;i < numsSize;i++)
14.   {
15.     if (nums[i] != val)
16.     {
17.       newArr[k++] = nums[i];
18.     }
19.   }
20.   //再把newArr数组的元素放到nums数组中
21.   for (int i = 0;i < k;i++)
22.   {
23.     nums[i] = newArr[i];
24.   }
25.   //销毁newArr数组
26.   free(newArr);
27.   newArr = NULL;
28.   return k;
29. }

复制代码

思路2

  第二种思路不太好想，但是代码非常简洁，且很多算法都能用到，这个方法就是双指针法，双指针算法是指我们先定义两个指针（在这里实际是整型变量，代表下标），一个src指针，一个dest指针，我们让src，dest开始都指向0，然后让dest每次++，++之后没种环境有不同的处理环境，分为以下两种：

1. 1） nums[src] == val，直接让src++
3. 2） nums[src] != val，那么先让nums[dest] = nums[src]，
4.     然后dest++，src++

复制代码

执行过程如图所示：
 

通过运行流程就可以看到，执行到末了dest的值就是nums数组中不为val值的个数，以是末了返回dest就可以了。 
   代码实现：

1. int removeElement(int* nums, int numsSize, int val)
2. {
3.     //定义两个变量
4.     int dest = 0,src = 0;
5.     //循环遍历数组
6.     while (src < numsSize)
7.     {
8.         //如果nums[src] == val,src++
9.         if (nums[src] == val)
10.         {
11.             src++;
12.         }
13.         //如果nums[src != val]
14.         else
15.         {
16.             nums[dest] = nums[src];
17.             src++;
18.             dest++;
19.         }
20.     }
21.     return dest;
22. }

复制代码

   固然，这个代码可以再优化，我们可以看到不管两种环境的哪一种环境，末了都是src++，以是我们只判断nums[src] != val的环境就可以了，以是优化后的代码就酿成了如许：

1. int removeElement(int* nums, int numsSize, int val)
2. {
3.     //定义两个变量
4.     int dest = 0,src = 0;
5.     //循环遍历数组
6.     while (src < numsSize)
7.     {
8.         //如果nums[src != val]
9.         if (nums[src] != val)
10.         {
11.             nums[dest] = nums[src];
12.             dest++;
13.         }
14.         src++;
15.     }
16.     return dest;
17. }

复制代码

  对于第二种算法头脑双指针法，许多标题中都可以用到，以是肯定要好好明白，信赖大家肯定可以掌握的。 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。