本文将对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;}