这篇博文向大家介绍几道最近刚学的基于顺序表的算法题因为看完讲解后我直呼秒啊~所以想赶快和大家分享文章目录1、移除元素2、删除有序数组中的重复项3、合并两个有序数组1、移除元素移除元素先看题目描述再来讲解解题思路题目要求我们原地移除数组中所有等于val的元素并返回移除后数组的新长度。所谓「原地」就是不能额外开辟一块和原数组等大的空间来存放结果只能在原数组的存储空间上做文章同时题目还特别说明元素的顺序可以改变不需要保持原有相对顺序返回的新长度之后的元素是什么内容也无所谓。这一点很关键它意味着我们不必像删除顺序表中间元素那样老老实实地把后面所有数据整体前移从而为后面的优化留出了空间。下面给出三种思路其中思路一、思路二供参考思路一的算法复杂度较高思路二虽然快但不符合「原地移除」的题目条件所以重点看思路三的双指针解法。intremoveElement(int*nums,intnumsSize,intval){inti0;while(inumsSize){if(nums[i]val){for(intji;jnumsSize-1;j){nums[j]nums[j1];}numsSize--;}else{i;}}returnnumsSize;}思路二创建新数组新数组的空间大小和原数组的一样大遍历原数组将值不等于val的数据放到新数组中去最后将新数组中的数据拷贝回原数组。具体来说用一个下标j记录新数组中已经存放了多少个有效元素遍历原数组时只要当前元素不等于val就把它依次放进新数组的第j个位置然后j自增遍历结束后j恰好就是保留下来的元素个数再把新数组前j个元素逐个拷贝回原数组即可。这个方法用空间换取了时间时间复杂度为O(n)空间复杂度为O(n)。相比思路一它把「边找边挪」的双层循环压缩成了一趟遍历效率明显提升但代价是多开了一块和原数组等大的辅助空间当数组规模很大时这份额外开销并不划算。intremoveElement(int*nums,intnumsSize,intval){intnewArr[numsSize];intj0;for(inti0;inumsSize;i){if(nums[i]!val){newArr[j]nums[i];}}for(inti0;ij;i){nums[i]newArr[i];}returnj;}由于题目要求原地移除所以以上解法不符合题目要求。思路三这个思路就略显巧妙了只需定义两个临时变量就可以获得O(n)的时间复杂度和O(1)的空间复杂度。我们称第三种方法为双指针法。首先创建两个变量dst和src(dst destinationsrc source一个是源一个是目的在有些情况下需要将源位置的数据赋值给目的位置所以这样取名。)都初始化为0“指向”下标为0的位置。然后开始比较拿src位置的数据同val进行比较。如果相等说明这个元素是要被移除的直接让src往后走跳过它对应于代码if(nums[src] val) src;如果不相等说明这个元素需要保留就把src位置的数据赋值给dst位置然后两个指针同时往后走对应于代码if(nums[src] ! val) { nums[dst] nums[src]; dst; src; }这里有一个容易忽略的细节当dst和src指向同一个位置时nums[dst] nums[src]相当于自己赋值给自己虽然结果没错但属于多余操作。不过这种「多余」换来的是代码逻辑的统一——不用额外判断两个指针是否重合可读性更好实际运行中这点开销也可以忽略不计。双指针法src快指针在前面探路从头到尾遍历数据负责扫描每一个元素dst慢指针标记下一个合法元素应该存放的位置。最后dst的值正好是数组中有效元素的个数。换个角度理解src走过的区域是「已经检查过」的部分dst走过的区域是「已经整理好」的部分而dst永远追不上src所以把src处的元素写到dst处时绝不会覆盖掉还没检查的数据。整个过程中每个元素最多被访问一次、被写入一次因此时间复杂度为O(n)又因为只用了两个整型变量没有开辟额外数组空间复杂度为O(1)完美满足题目「原地移除」的要求。具体实现intremoveElement(int*nums,intnumsSize,intval){intsrc0;intdst0;while(srcnumsSize){if(nums[src]!val){nums[dst]nums[src];dst;}src;}returndst;}思路三用for循环是这样实现的把src的自增交给for循环的第三部分代码会更紧凑一些intremoveElement(int*nums,intnumsSize,intval){intsrc0;intdst0;for(src0;srcnumsSize;src){if(nums[src]!val){nums[dst]nums[src];dst;}}returndst;}前面介绍了双指针法接下来再来看两道可以利用双指针法解答的题目。2、删除有序数组中的重复项删除有序数组中的重复项先看题目描述再来讲解解题思路思路创建两个变量src和dst分别“指向”起始位置和下一个位置这两个变量其实是用作数组的下标并非指针。当下标为src的元素等于下标为dst的元素时src往前走对应于代码if(nums[src] nums[dst] src;)当下标为src的元素不等于下标为dst的元素时dst往前走再把下标为src的元素赋值给下标为dst的元素让src往前走,对应于代码if(nums[src] ! nums[dst]) { dst; nums[dst] nums[src]; src; }。最后有效元素个数就是dst1。intremoveDuplicates(int*nums,intnumsSize){intdst0;intsrcdst1;while(srcnumsSize){if(nums[src]!nums[dst]){dst;nums[dst]nums[src];}src;}returndst1;}在以上代码中当下标为src的元素不等于下标为dst的元素时如果每次dst走到src的位置再将下标为src的元素赋值给下标为dst的元素很多余此时等同于自己赋值给自己所以需要将代码优化一下intremoveDuplicates(int*nums,intnumsSize){intdst0;intsrcdst1;while(srcnumsSize){if(nums[src]!nums[dst]dst!src){nums[dst]nums[src];}src;}returndst1;}3、合并两个有序数组合并两个有序数组先看题目描述再来讲解解题思路思路一先将两个数组合并再利用排序算法进行排序。冒泡排序的时间复杂度为O(n²)不推荐voidmerge(int*nums1,intnums1Size,intm,int*nums2,intnums2Size,intn){intk0;while(kn){nums1[m]nums2[k];}for(inti0;im-1;i){for(intj0;jm-i-1;j){if(nums1[j]nums1[j1]){inttmpnums1[j];nums1[j]nums1[j1];nums1[j1]tmp;}}}思路二创建新数组空间大小和nums1一致遍历两个原数组中的数据比较大小并按顺序放到新数组中最后拷贝回nums1数组中。时间复杂度为O(mn)空间复杂度为O(mn)。不推荐voidmerge(int*nums1,intnums1Size,intm,int*nums2,intnums2Size,intn){intnewArr[nums1Size];inti0,j0,k0;while(imjn){if(nums1[i]nums2[j]){newArr[k]nums1[i];}else{newArr[k]nums2[j];}}while(im){newArr[k]nums1[i];}while(jn){newArr[k]nums2[j];}for(inti0;ik;i){nums1[i]newArr[i];}}思路三定义三个整型变量都表示下标。l1“指向”num1中的最后一个元素l2“指向”nums2中的最后一个元素nums3“指向”nums1空间的最后一个位置。然后比较l1对应的空间元素和l2对应的空间元素的大小谁大谁就往l3的位置上放然后两个下标同时减一。实际上就是从后往前比较大小大的往后放。最后处理结束时的情形l1和l2必定有一个先小于0,此时退出while循环。当l2先小于0时l1下标对应的元素及其前面的元素也已经是有序的所以无需其他操作当l1先小于0时需要把l2“指向”元素及其之前的元素移动到num1中l3指向的位置。voidmerge(int*nums1,intnums1Size,intm,int*nums2,intnums2Size,intn){intl1m-1;intl2n-1;intl3mn-1;while(l10l20){if(nums1[l1]nums2[l2]){nums1[l3--]nums1[l1--];}else{nums1[l3--]nums2[l2--];}}while(l20){nums1[l3--]nums2[l2--];}妙啊~~吸吸智慧