知名做网站公司有哪些,网站制作建设有哪些,婚纱设计网站,工会网站建设方案目录 题目#xff1a;合并两个有序数组
题目分析方向1#xff1a;
题目分析方向2#xff1a; 题目#xff1a;合并两个有序数组
题目要求#xff1a;
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2#xff0c;另有两个整数 m 和 n #xff0c;分别表示 nums…目录 题目合并两个有序数组
题目分析方向1
题目分析方向2 题目合并两个有序数组
题目要求
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。 示例 1
输入nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3
输出[1,2,2,3,5,6]
解释需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] 其中斜体加粗标注的为 nums1 中的元素。示例 2
输入nums1 [1], m 1, nums2 [], n 0
输出[1]
解释需要合并 [1] 和 [] 。
合并结果是 [1] 。示例 3
输入nums1 [0], m 0, nums2 [1], n 1
输出[1]
解释需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意因为 m 0 所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。提示
nums1.length m nnums2.length n0 m, n 2001 m n 200-109 nums1[i], nums2[j] 109 进阶你可以设计实现一个时间复杂度为 O(m n) 的算法解决此问题吗 题目分析
题目分析方向1
首先我们看到这个是个有序数组因此可以考虑使用归并的思想合并两个有序数组。
那我们可把上面的nums1和nums2的数据尾插到新的数组来nums3
规律1依次比较取小的尾插到新数组nums3里面也就是把最小的数据取出来放到新的数组nums3里面。
规律2数据大小相同则随便取nums1或者nums2数组中的一个数据即可。
因为是非递减数列那么该数组的数组从前到后要么就是比前面大要么跟前面相等。
大小数据是n
那么这个归并的时间复杂度是经典的On; 那么尾插到nums3数组后的数据结果为为nums3{1,2,2,3,5,6}
如果是这种有序数据我们是不是有些人会想如果使用冒泡排序也是可以实现啊。
那如果我们假设两个数组的长度是N
那么使用冒泡排序的时间复杂度就是ON2
那么使用qsort 快速排序也是O(N*log2N)log2N,就是以2为低的对数。
从以上的分析使用归并的思想也是可以将上面两个有序数组进行排序但是很显然这个是不符合题目要求的因为题目的要是是合并后的数据存放到nums1中。
但是在有序无序的数据如nums1{2,2,3,0,0,0};nums2{1,5,6};如果nums2[0]nums1[0],那么nums2[0]的值就覆盖到nums1[0]里面这个就会导致原本数组数据不对了。
因此这里我们得另想他法
题目分析方向2
既然分析方向1的解法只适合有序的的数组那么归并的方法就显得不合适了。
这里我想到了一个方法就是从后往前比较。
画图吧 从图中我们可以知道两个有序数组进行第四次比较的时候就完成了两个数组的合并。
当完成第四次比较之后我们知道nums2是位于首元素位置而nums1则位于元素1位置。
那么我们可能会问nums1并没有比较遍历全部元素是否还需要剩下的元素进行排序
结果显然是不需要的。因为nums1中剩下的元素位于数组的低地址处本身属于有序数组因为不需要再进行比较。
那么代码上是怎么实现的呢
在这里解释一下部分代码
nums1[i--]会先返回nums[i]的值也就是此刻参与计算的还是nums[1]的值同时i--让i指向下一个元素。
并且从运算的逻辑来看i--属于先赋值后运算的符号。 void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int im-1;int jn-1;int kmn-1;while(i0 j0){if(nums1[i]nums2[j]){nums1[k--]nums1[i--];}else{nums1[k--]nums2[j--];}} while(j0){nums1[k--]nums2[j--];}}
