【OJ】关于顺序表的经典题目（移除数组中指定元素的值、数组去重、合并两个有序的数组）

前言

通过有关顺序表的知识讲解,相信大家或多或少都对顺序表有一定的了解。

那么在本文中，我们将会给出几道有关于顺序表(个人觉得于数组的相关性较大)经典的代码练习题，并且总结一些做题的经验，呈现给大家。

题目1：移除数组中指定的元素

题目链接：移除元素 - LeetCode

题目描述

解题思路

方法1 ：暴力法

相信很多人看到这道题的时候，会不自觉的这样想：我先遍历题目所给的数组，在遍历的过程中，将每个数组中的每个元素与题目所给的那个val进行比较。如果不相等的话，我就把那个元素赋值到我新建的数组中。

由于这个想法比较简单，这里我就不画图进行讲解了。

实现的代码如下：

//方法1：暴力法
#include<stdlib.h>
int removeElement(int* nums, int numsSize, int val) {//创建一个与题目所给数组一样大小的空间int* newnums = (int*)malloc(sizeof(int)*numsSize);if (newnums == NULL){perror("malloc fail");exit(1);}//开始进行删除数据int i = 0;int count = 0;while (i < numsSize){if (nums[i] != val){newnums[count++] = nums[i];}i++;}return count;
}

方法2：双指针法

相信经过上面的描述，已经对双指针的用法有了初步的感觉了！如果还不会的话，不用担心，本文后面的题目仍会用到双指针法的。

实现的代码如下：

int removeElement(int* nums, int numsSize, int val) {//创建两个指针，但对于数组来说下表的移动也可以相当是指针的移动int src = 0, dst = 0;while (src < numsSize){if (nums[src] != val){nums[src++] = nums[dst++];}else{src++;}}return dst;}

---

题目2：数组去重

题目链接：数组去重 - LeetCode

题目描述

解题思路

这题的难点在于原地删除重复出现的元素，这个就意味着我们无法像上面那道题一样创建新数组去完成了。

那该怎么办呢？在仔细看一下条件，题目还说了数组的元素是非严格递增排列的。但是我们有前面移除数组元素题目做铺垫，这两道题的共性都在于删除元素。

那我们可以先用双指针法来尝试做一下这道题！

这里你会发现，指针src就像一个侦察兵，dst指针就像一个大本营。当指针src发现前面有埋伏时，它就会跟大本营说，前面有埋伏，你不要过来，让我看看还有哪个地方时没有敌人的埋伏的。当发现没有埋伏是，大本营就会根据src传递的信息记录下这个没有埋伏的地方！

看到这里，你会发现：噢，双指针法真的能解决这个问题。但是你再仔细思考一下，如果数组是乱序的话，还能不能这样做？
很显然是不能的，因为dst指针指向的位置一旦被赋值之后，dst指针就会往下挪动一个位置。那假如，src在数组很后面的位置找到了dst之前那个位置的值，那就没有办法检测到了。

双指针法

代码实现：

//双指针法
int removeDuplicates(int* nums, int numsSize)
{int dst = 0, src = 1;while (src < numsSize){if (nums[dst] == nums[src]){//说明，src位置的元素是重复出现的。我们就要记录下来这个位置。//做法就是,我们可以先不动dst位置，等到值不一样的时候，再移动并赋值。src++;}else{nums[++dst] = nums[src++];}}return dst+1;
}

可能有的读者这里会问，能不能在nums[dst] == nums[src]的时候，将dst和src指针都移动一个位置。答案是不能！
自己画图就可以理解这一点了。

也许看到这里，你会说双指针法很好用！确实，它非常的好用！

---

题目3：合并两个有序的数组

题目链接：合并两个有序的数组 - LeetCode

题目描述

解题思路

按照题目的要求给了我们两个非递减顺序排列的数组。目的就是让我们合并它们，并且合并之后数组是按照非递减顺序排列的。

那该怎么做呢？我们在没有思路时，可以先去看一下题目给出的一些案例。不过我相信有一个方法是大家都能想到的，这里我姑且叫它暴力破解法

方法1：暴力破解法

将两个有序数组合并成一个数组之后，在使用排序算法，将它变成有序的！没错这个方法的确可行。

代码实现如下：

//思路：先将两个数组合并之后，再排序
#include<stdlib.h>
int compare_int(const void* x, const void* y)
{return *((int*)x) - *((int*)y);
}void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {//申请一块地址空间，用于存放两个数组合并之后的数组int* nums = (int*)malloc(sizeof(int) * (m + n));if (nums == NULL){perror("malloc fail");exit(1);}int count = 0;for (int i = 0; i < m; i++){nums[count++] = nums1[i];}for (int i = 0; i < n; i++){nums[count++] = nums2[i];}//这里使用qsort函数进行排序qsort(nums,m+n,sizeof(int),compare_int);}

方法2：从后往前

代码实现：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int n1 = m -1 , n2 = n - 1;int end = n1 + n2 + 1;while(n1 >= 0 && n2 >= 0){if(nums1[n1] > nums2[n2]){nums1[end--] = nums1[n1--];}else{nums1[end--] = nums2[n2--];}}//循环退出之后，一定有个数组还未遍历完。//如果是nums1这个数组未遍历完，其实可以不用给它单独处理//因为，题目要求返回的是nums1//如果是nums2的话，那就要给它处理一下while(n2 >= 0){nums1[end--] = nums2[n2--];}//}}

到这里，我们习题就已经全部讲完了。

本文主要讲解了一种解题方法：双指针法，针对这个方法，我会还会再出题目的讲解的!

如果觉得本文讲的还不错的话，麻烦给偶点个赞吧！！！