题目内容:
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。
注意:最终合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。
leetcode题目链接(点击即可跳转):
思路分析
看完题目,我们先别火急火燎的去编程做题,而是要先仔细理解题目的意思。(某些同学这时候可能会说“不是吧,不是吧,题目内容都给出来了,不会还有人看不懂吧?不会吧,不会吧!”)实际上,可能很多小伙伴们刚上手OJ题时(online judge 在线编程题)都不会很认真去审题,而是直接编程,然后报出一大堆错误,一个个调试,最后。。。就没有最后了,真的是“从入门到放弃~”。因此,为了避免这个问题,更加高效和正确的练习,我们应该要“理解题目—思路分析(画图理解)—极端场景—动手编程—回顾总结”。这些步骤看起来好像挺繁琐的,但是实际上花的时间比直接上手编程还要少,而且最终的学习、练习效果也要好上不少。
(当然,分享博客也可以帮助我们梳理做题的思路,总结做题的经验和方法,最最最重要的是能帮助到其他人,然刷题的这个过程多了一些“其他的意义”)
那么问题来了,如何更好的理解题目呢?
(1)将题目看完后,用自己的话复述出来,只需要大概的意思相同即可。
比如说这道题目,题目大概的意思就是“有两个整体而言升序(就是中间可能存在相等的元素,不是严格升序,这就是对”非递减排列“的理解)的数组num1,num2。num1有m个元素,但是长度为m+n,num2有n个元素,长度为n。现在要求我们将两个数组合并成一个数组并存放到num1当中,排序方式跟之前一样。”
(2)从多个角度给自己提问
比如说:
①题目有要求说不能开辟临时数组吗?或者说要求空间复杂度为O(1),又或者是原地处理数据。(显然本题是没有这个要求的!)
②题目中有说m、n不能等于0吗?如果等于0时该怎么处理?
③题目中对时间复杂度有要求吗?(进阶部分要求时间复杂度为O(n+m)
方法一:临时数组法
既然题目中没有要求“原地”合并数据,那么我们应该很容易想到建立一个长度为n+m的临时数组,先将num1,num2两个数组中的内容按照“不降序”方式放到临时数组中,然后将临时数组中的内容拷贝回num1数组中。
这种方式对于题目②出现的情况:
1)m=0、n=0 不符合题目提示中 1 <=
m+n的情况。(其实我还有点好奇如果真遇到了,m=n=0,m+n=0,怎么处理,能创建长度为0的临时数组吗?长度为0的数组有意义吗?m=0时只是代表num1中没有有效元素,但是实际的长度不为m,而是n+m >=1。如果真遇到了,都不用开辟临时数组,直接处理即可)
2)m=0、n>0,也就是说num1中无有效元素,num2中有n个有效元素,这个时候就会将num2中的数据先全部放到临时数组中,然后从数组中拷贝到num1中,可以解决问题,不会出现错误(虽然效率有点低,但好歹解决问题了,问题不大)
3)n=0、m>0,也就是说num2中无有效元素,num1中有m个有效元素,这个时候就会将num1中的数据先全部放到临时数组中,然后从数组中拷贝到num1中,可以解决问题,不会出现错误。(额,看起来呆呆的)
所以整体来看,临时数组的方式不会出现太大的问题,这个时候就可以画出图解,编写代码测试了。
算法图解
函数接口实现
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){int* arr = (int*)malloc((m+n)*sizeof(int));//创建长度为m+n的临时变量int src1 = 0;//nums1的起始下标int src2 = 0;//nums2的起始下标int dest = 0;//arr的起始下标while((src1 < m) && (src2 < n)){if(nums1[src1] <= nums2[src2]){//将nums1的元素赋给arr,两个数组下标同时向后移动arr[dest++] = nums1[src1++];}else{//将nums2的元素赋给arr,两个数组下标同时向后移动arr[dest++] = nums2[src2++];}}//走到这里,表示num1或num2有一个已经结束了if(src1 == m){//src1 = m表示num1中的有效元素全部移到arr中了//只需要将num2中的元素全部移到arr中即可while(src2 < n){arr[dest++] = nums2[src2++];}}else{//src2 = n表示num2中的有效元素全部移到arr中了//只需要将num1中的元素全部移到arr中即可while(src1 < m){arr[dest++] = nums1[src1++];}}//最后将arr中的元素拷贝给num1for(int i = 0; i < (n+m); i++){nums1[i] = arr[i];}//释放动态开辟的数组free(arr);arr = NULL;}
上述的这种使用临时数组的方法,我们再将num1、num2中的元素移到临时数组时,采用了从num1、num2两个数组的起始端到终止端的方式,也就是说采用了“从前往后”的方式。那么我们可不可以采用”从后往前“的方式呢?(既然我都问了,那我自然就不能”光说不做假把戏“)
方法二:临时数组倒立版
(别问为什么叫倒立版,为什么不叫翻转版、逆序版、反向版???问就是我感觉”倒立版”三个字比较“霸气”,对,就是比较“霸气”,有木有一种“霸气外露”的感觉?)
这种方法只需要在原来临时数组法的基础上进行一些调整即可,主要是将src1、src2两个下标从之前的“从前往后”遍历变成“从后往前”遍历,那么两者比较的时候,就是谁大,谁就保留到临时数组arr中,注意临时数组也需要从后往前遍历。
算法图解
函数接口实现
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){int* arr = (int*)malloc((m+n)*sizeof(int));//创建长度为m+n的临时变量int src1 = m - 1;//nums1的终止下标int src2 = n - 1;//nums2的终止下标int dest = m + n - 1;//arr的终止下标while((src1 >= 0) && (src2 >= 0)){if(nums1[src1] >= nums2[src2]){//将nums1的元素赋给arr,两个数组下标同时向前移动arr[dest--] = nums1[src1--];}else{//将nums2的元素赋给arr,两个数组下标同时向前移动arr[dest--] = nums2[src2--];}}//走到这里,表示num1或num2有一个已经结束了if(src1 < 0){//src1 < 0表示num1中的有效元素全部移到arr中了//只需要将num2中的元素全部移到arr中即可while(src2 >= 0){arr[dest--] = nums2[src2--];}}else{//src2 < 0表示num2中的有效元素全部移到arr中了//只需要将num1中的元素全部移到arr中即可while(src1 >= 0){arr[dest--] = nums1[src1--];}}//最后将arr中的元素拷贝给num1for(int i = 0; i < (n+m); i++){nums1[i] = arr[i];}//释放动态开辟的数组free(arr);arr = NULL;}
使用临时数组的方法,虽然可以解决问题,但是我们假设出现这样一种情况“需要合并的两个数组很大,也就是m+n很大”,那么我们需要创建的临时数组的空间就越大,空间复杂度为O(n+m)。上面的两种临时数组方法时间复杂度都是O(n+m),也就是说符合进阶版的要求。
时间复杂度、空间复杂度相关文章:
【数据结构学习笔记】一、数据结构介绍及算法分析(新手入门进阶指南)
那么有没有一种方法既可以不开辟临时数组,又可以达到类似临时数组的效果呢?(也就是说时间复杂度不变,为O(n+m),但是空间复杂度变成了O(1))
答案当然是“有!”,这种方法我愿称之为“超级进阶版,豪华进阶版,终极plus版”,至少目前我还找不到比这种方法还高效的算法了。
方法三:虚拟数组法(超级豪华终极puls版)
这种方法可以说是从“临时数组倒立版”发展而来(至少我是这么想到的),倒立版中两个数组从后往前遍历将较大的数保存到临时数组中。实际上可以不用放到临时数组里面,而是可以直接放到num1里面。因为num1本身的长度是够了(m+n)且num1后面的n个位置是不放有效数据的,不用担心数据被覆盖掉。(如果你要从前往后遍历就需要担心将原来num1中的数据给覆盖了)最后将临时数组内容拷贝回num1中的这一步可以省略。(此处应该有“666、Nb、我滴天啦!”)
算法图解
函数接口实现
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){int src1 = m - 1;//数组nums1有效元素的终止下标int src2 = n - 1;//数组nums2的终止下标int dest = m + n - 1;//数组nums1整体的终止下标while(src1 >= 0 && src2 >=0){if(nums1[src1] >= nums2[src2]){//将nums1的src1指向的元素赋给nums1的dest指向的位置//两个数组下标同时向前移动nums1[dest--] = nums1[src1--];}else{//将nums2的src2指向的元素赋给nums1的dest指向的位置//两个数组下标同时向前移动nums1[dest--] = nums2[src2--];}}//走到这里代表src1或src2走完了if(src1 < 0){//如果是src1提前走完,将nums2中元素全部拷贝给nums1while(src2 >= 0){nums1[dest--] = nums2[src2--];}}//如果是src2提前走完,不需要进行任何处理}
原创不易,各位小伙伴点个赞,评个论,光个注呗~
你们的支持将是我前进的最大动力!!!