ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【C】顺序表算法题 -- 移除元素 [打印本页]
作者: 西河刘卡车医    时间: 2025-1-17 05:32
标题: 【C】顺序表算法题 -- 移除元素
  同样的，了解了顺序表的实现之后，我们就该通过算法题来巩固顺序表了，接下来我们就来一道算法题移除元素。
leetcode链接
https://leetcode.cn/problems/remove-element/description/
我们来看一下标题的描述：
给你一个数组 nums 和一个值 val，你必要 原地 移除所有数值即是 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不即是 val 的元素数量为 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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4