LeetCode.26,27,88三题-双指针的运用

本文将对3道解决方法类似的题目进行逐一分析，这三道题目分别是：

LeetCode.26 删除有序数组中的重复项

LeetCode.27 移除元素

LeetCode.88 合并两个有序数组

1. LeetCode.27 移除元素：

题目内容如下：

 假设一个数组为：

nums = [0,1,2,2,3,0,4,2]

元素.

按照题目的要求，需要移除数组中所有等于的元素。对于此题的解析，文章提供三种参考思路

1.在之前处理顺序表中删除元素的问题时，采用的方法是将目标元素后面的元素全部向前覆盖一位。但是，这种处理方法的时间复杂度为过于缓慢。

2.创建一个指针和一个新的数组，遍历整个数组，在便利的过程中。若被遍历的元素大小不等于时，将此元素复制到新开辟的数组中。当被遍历的元素大小等于时，不复制并且将指针指向下一个元素。此方法的时间复杂度为，相对于方法1，大幅度降低了程序执行所用的时间。但是，该方法因为新创建了一个数组。空间复杂度为，不符合题目中的要求。

3. 虽然方法不满足题目的要求，但是可以通过方法的思路来延伸出方法，也就是文章题目中提到的双指针法。

对于本题，双指针法的具体用法如下：

1.创建两个指针，这里创建的指针分别命名为。最开始，两个指针都指向数组首元素的下标，即：

 对于本题中创建的两个指针的动作，总结下来就是：将数组中位置上不等于的元素放置到中。

当两个指针所对应的元素相等且不等于时，都指向下一个元素。

当指针对应的值等于时，指针指向下一个位置，不移动

当两个指针对应的元素不同且不等于时，将指针对应的元素赋值到位置。并且都向前移动一位。

用图片表示下列过程，即：

1.

 2.

此时， 指针对应的值等于。所以指针不动，指针继续向后移动：

此时，指针 对应的值不等于，并且不等于。所以，进行赋值操作：

 再次向后移动，还会重复上面的动作：

当 遍历整个数组后，数组中内容如下图所示：

上述过程对应的代码为：

int removeElement(int* nums, int numsSize, int val){int dst = 0;int src = 0;while( src < numsSize){if( nums[src] != val){nums[dst++] = nums[src++];}else{src++;}}return dst;}

 2. LeetCode.88 合并两个有序数组：

题目如下：

 

给出的示例如下：
 

 用图片表示上面给出的示例，即：

 对于这道题的解法，依旧采用双指针的思想，对于每一个数组均创建一个指针。但是，如果再次采用上面从头到尾进行遍历的方法，如果再某处需要插入元素，则还是会出现顺序表中插入元素出现的问题，即：每插入一个元素，都需要将后面的元素整体后移动一位。所以对于此题。最好采用从后向前，从大到小的顺序进行遍历。并且，将第一个数组中最大的元素与第二个数组中的元素分别进行比较。较大的则插入到第一个数组中后面的区域，将上述过程用图片演示，即：

 上面的情况中，是第二个数组元素全部遍历完成时，第一个数组中的元素没有完成遍历。但是对于下面的情况，即：第一个数组完成遍历时，第二个数组并没有完成遍历：

用图片表示上述数组中元素的变化情况：

 ​​

 

 最后的结果如上图所示： 第二个数组中的元素并没有插入到第一个数组中。并且第一个数组已经遍历完成。而第二个数组没有遍历完成。

总结上述过程，为了方便陈述，将第一个数组命名为，将第二个数组命名为。

为创建的指针命名为，为创建的指针命名为。

从后向前对两个数组同时遍历，

当满足对应的元素＞对应的元素时，将对应的元素在中进行一个尾插操作。并且两个指针均指向前一个元素。

当不满足上述关系时，将对应的元素在在前面插入元素的基础上进行一个尾插操作。并将指向前一个元素。

当遍历完成时。标志着程序运行完成。当遍历完成但是没有完成遍历时。将剩余的元素在中进行插入。

用代码表示上述过程：

首先，题目中已给的参数分别是：

m表示 中非的元素。n表示中的元素。为了方便表示，用表示上面的参数。表示中加上0元素的总长度。

代码如下：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){int end1 = m - 1; int end2 = n -1;int end = m + n -1;while( end1 >= 0 && end2 >= 0){if( nums1[end1] > nums2[end2]){nums1[end--] = nums1[end1--];}else{nums1[end--] = nums2[end2--];}}while( end2 >= 0){nums1[end--] = nums2[end2--];}}

3. LeetCode. 26 删除有序数组中的重复项：

题目如下：

 示例如下：

依旧采用双指针的方法来结局问题。创建两个指针分别为,

从上面的题目要求可知。题目涉及到对于数组中元素的更改。所以，创建的两个指针在开头可以处于相同位置，也可以处于不同位置。为了方便演示，这里给出不同位置的情况，例如下面图片所示的数组：

 

 因为要保证数组中元素不能重复，所以，需要将后面的元素覆盖到前面元素的位置。所以，需要一个指针取读取后一位的元素，并且与前一位的元素进行对比。此时如果后一位元素与本位元素相同。则指向后一个元素：

 此时，两个指针指向的元素不同，所以，先让指向后一位元素，再将中的元素赋值给此时的，再,此时两个指针指向的元素相同，所以一直，直到：

 重复上面所说的步骤，即：

 

 按照前面说的规则，最后的效果为

 

通过图片不难发现，程序结束的标志就是当指针 数组中元素个数时（或者数组中元素个数时）。

总结上述过程，可以分为三个要点：

1.  数组中元素个数时，程序结束

2.指向的值=时，指向后面的元素。不变。

3. 指向的值不等于时，先将,再将指向的值赋值到，最后+1.

用代码表示，即：

int removeDuplicates(int* nums, int numsSize){int dst = 0;int src = 1;while( src < numsSize){if( nums[src] == nums[dst]){src++;}else{dst++;nums[dst] = nums[src];src++;}}return dst+1;}