网站空间位置是什么,wordpress图标,程序员培训比较好机构有哪些,考试源码网站wordpress本文将对3道解决方法类似的题目进行逐一分析#xff0c;这三道题目分别是#xff1a;
LeetCode.26 删除有序数组中的重复项
LeetCode.27 移除元素
LeetCode.88 合并两个有序数组 1. LeetCode.27 移除元素#xff1a;
题目内容如下#xff1a; 假设一个数组为#xff1…本文将对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 dst1;}
