【初阶数据结构】——双“指针”求解顺序表（数组）常见问题
【初阶数据结构】——双“指针”求解顺序表（数组）常见问题
前言
这篇文章，我们一起来看几道数组相关的面试题。
每道题目，我们给出的解题思路可能都不止一种，我们要不断分析讨论，找出最优的解题思路来实现。 一起来看看吧！！！
题目1：移除元素
题目链接放在这里，供大家练习：链接: link 先来看一下题目吧：
题目是什么意思呢？
其实就是给我们一个数组，还有一个值val，我们要删除这个数组中所有值和val相等的元素，然后返回删除之后的新数组的长度。
那怎么解决呢？接下来我们一起来分析一下：
思路1：暴力求解
思路1就是暴力求解，这也是我们可能最先会想到的一个方法：从头到尾找一个删除一个。
怎么做呢？
从数组的第一个元素开始，向后遍历，如何当前元素的值等于val的值，就删除。 怎么删呢？ 将后面的元素，依次向前移动，将要删除的元素覆盖掉。后面也是如此，直至将数组中所有值等于val的元素都删除掉，就完成了。
那大家思考一下，这个方法好不好？
肯定是不太好的，如果给的数组中有大部分元素的值都等于val，比如像这样：
val的值是2，数组中所有等于2的元素，都要删除，每次删除都要挪动数据，等于val的元素越多，挪动的次数就越多，有些数据就会被不断地，重复的挪动，这样它的时间复杂度其实可以认为是O(N^2)，效率就可能会比较低。
那这种方法我们就不实现了，我们再思考思考有没有更优的解法。
思路2：空间换时间
第一中解法暴力求解，它的时间复杂度太大了，那有没有更好的方法呢？
这里提供一种空间换时间的解法。
具体思路是这样的：
我们再额外创建一个数组，假设命名为tmp，然后对原数组进行遍历，如果当前元素不等于val，就把他拷贝到tmp数组中，如果等于val，不做处理，这样遍历结束，tmp数组中放的就是删除之后的元素，然后我们把tmp中的元素再拷贝回原数组，tmp的大小就是要返回的新长度。
那这种思路，它的**时间复杂度就是就是O(N)**了，与第一种方法的O(N^2)相比，就好很多了。
但它的的缺点在于：
我们又额外开辟了一个数组，该数组的大小与原数组等大，因此它的空间复杂度也是O(N)。这是他不好的地方。 而且呢，题目也要求：
所以，这还没有完，我们要继续优化，找出一个即效率高，还不用开辟额外空间的算法。
那有没有这样的解法呢？
当然有，其实我们对解法2再稍做优化，就行了。
思路3：双指针原地删除（解法2的再优化）
其实思路还是2的思路，只不过这次我们不再另外开辟一个新的数组了。
那要怎么搞呢？
思路分析
这里我们定义两个变量作为两个指针（注意这里说的指针只是一个形象化的称谓，不是用来存储地址的指针变量），开始它们都指向0下标的位置。
然后呢：
我们src指向的元素和val比较，如果不相等，就把src指向的元素赋值给dest指向的元素，即
nums[dest]=nums[src]，然后让dest和src都++。 然后再让src指向的元素和val比较，不相等继续上述操作，如果相等了，我们只让src++往后走，dest不动，然后再让src指向的元素和val比较，看是否等于val。 直至遍历完整个数组。
代码实现
那现在思路理清了，图也画出来了，接下来写代码就很简单了：
直接上代码：
int removeElement(int* nums, int numsSize, int val){
int src=0;
int dest=0;
while(src<numsSize)
{
if(nums[src]!=val)
{
nums[dest++]=nums[src++];
}
else
{
src++;
}
}
return dest;
}
题目2：删除有序数组中的重复项
链接分享给大家：链接: link 一起看一下题：
这道题呢，其实就是让我们去重，数组中有些值重复出现，我们要让所有的元素都只出现一次，最终还是返回新数组长度。
这道题怎么做呢？
比较简单的一种方法还是利用双指针来解决。
思路：双指针
那这个题该如何利用双指针求解呢？
首先，还是定义两个变量作为指针，初始都指向下标为0位置。
如果两指针指向的元素相等，我们只让 src++往后走，过滤掉重复值。
如果不再相等，先让dest++，让后把src指向的元素赋值给dest指向的元素，然后再让src++。
然后再判断两指针指向的元素是否相等，重复上述操作，直至src遍历完数组。
最终dest+1就是去重后的数组长度。
代码实现
上代码：
int removeDuplicates(int* nums, int numsSize){
int src=0;
int dest=0;
while(src<numsSize)
{
if(nums[src]==nums[dest])
{
src++;
}
else
{
// dest++;
// nums[dest]=nums[src];
// src++;
nums[++dest]=nums[src++];
}
}
return dest+1;
}
题目3：合并两个有序数组
链接: link
常规合并方法
首先我们思考一下，如果给我们两个非递减的数组，我们如何去合并它们。
其实用双指针的方法还可以搞定，举个例子：
假如现在有这样两个数组：
如何合并？
两个指针分别指向两数组第一个元素，再开辟一个新数组，对他们进行比较，依次取较小的那个元素放到新数组中，如果相等，任选一个放入。
但是，对于这个题，这种方法可行吗？
显然是不可行的。
题目分析
为什么不可行呢？
我们来看这道题：
它给我们两个按 非递减顺序 排列的整数数组 nums1 和 nums2，确定是要求我们，但是要求我们把合并后的数组放到nums1 中。 也就是说，nums1 提前把空间开好了，已经足够放得下合并之后的整个数组了，不需要我们再额外开辟新数组了。
那上面那种方法显然就不适用了。
那这种情况我们应该怎么搞呢？
就拿题中这个例子来看：
如果我们还像上面那样从前往后两两比较大小，还可以吗？ 如果nums2的的第一个元素就比nums1的小，那题目要求放到 nums1里，这样是不是就把nums2的第一个元素覆盖掉了啊。 所以这样搞不行。
那应该怎么办呢？
我们知道，nums1已经提前开好了多余的空间，这些空间在哪里啊，是在nums1有效数据的后面。
思路：三指针
所以我们怎么做比较好？
是不是从后往前倒着比较啊。 怎么比？ 要取出两者中较大的元素放到后面，后面的数据我们覆盖掉是没问题的。
那接下来我来画图带大家再梳理一下思路：
这里需要我们再增加一个指针。
指针i1，i2分别指向数组nums1和nums2的最后一个元素，注意nums1是有效数据的最后一个，然后加一个dest指向nums1的最后一个位置。
然后开始比较：
i1，i2指向的元素哪个大，就把该元素赋值给dest指向的元素，然后dest和对应的i1或i2向前移动一个位置，继续比较。
相等的话，我们随便给哪一个都行 我这里就选择把i1指向的值给dest。
这一步的代码就是这样：
然后继续走：
走到这个位置我们发现
i2就走完了，遍历结束了，那此时是不是就完成了啊
这就是最终的状态了。
所以：
如果是i2先走完，i2走完就结束了，完成了。因为这些元素本来就在nums1中，不需要动了。
那也有可能是i1先走完啊，i1先走完是不是也直接结束了呢？我们来分析一下：
看这种情况：
还是按上面的方法依次进行比较。
但是这次我们会发现：
这次是i1先走完，但是这样结束了吗。 还没有， 我们需要把nums2中剩下的元素再拷贝到nums1前面的位置。
所以要注意：
如果是i1先走完，我们还需要继续处理，把nums2中剩余的元素放到nums1中。
代码实现
所以最终代码应该是这样的
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int i1=m-1;
int i2=n-1;
int dest=m+n-1;
while(i1>=0&&i2>=0)
{
if(nums2[i2]>=nums1[i1])
{
nums1[dest--]=nums2[i2--];
}
else
{
nums1[dest--]=nums1[i1--];
}
}
while(i2>=0)
{
nums1[dest--]=nums2[i2--];
}
}再简单解释一下，相信大家就能很好的理解了：
首先说一下，题目里给的参数有些冗余
nums1Size和nums2Size其实不要也可以，因为nums1Size就是m+n，nums2Size就是n。
然后代码也简单提一下：
所以最终的代码就是这样。
好了，以上就是几个数组相关面试题的讲解，欢迎大家指正！！！