深圳营销型网站建设哪家好,南屏网站建设,关于网站建设实验报告,山东网站建设代理原题链接#xff1a;https://leetcode.cn/problems/merge-sorted-array/
目录
1. 题目描述
2. 思路分析
3. 代码实现 1. 题目描述 2. 思路分析
看到这道题#xff0c;我们注意到nums1[ ]和nums2[ ]两个数组都是非递减的。所以我们很容易想到额外开一个数组tmp[ ]#x…原题链接https://leetcode.cn/problems/merge-sorted-array/
目录
1. 题目描述
2. 思路分析
3. 代码实现 1. 题目描述 2. 思路分析
看到这道题我们注意到nums1[ ]和nums2[ ]两个数组都是非递减的。所以我们很容易想到额外开一个数组tmp[ ]依次比较两个数组的元素每次取小的尾插到新数组tmp[ ]即可。但是这需要额外再开空间。 也有一种方法是将这两个数组的元素都拷贝到一起然后使用qsort排序 复杂度为O(NlogN)。
显然这两种方法的复杂度都不够优秀是否有更好的方法呢 我们可以倒着比较取大的依次往前插入。等到有一个数组被遍历完就结束。
因为两个数组都是非递减的nums1[ ]数组的长度比nums2[ ]大所以如果nums1[ ]先被遍历完就将nums2[ ]没有被遍历的元素直接拷贝到nums1[ ]前面。
如果nums2[ ]先被遍历完则不用额外操作因为nums1[ ]整体本身就是非递减的所以那些没有被遍历到的元素也是按非递减排列的。
流程演示 3. 代码实现
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int end1 m - 1, end2 n - 1, end m n - 1;while (end1 0 end2 0){if (nums1[end1] nums2[end2])nums1[end--] nums1[end1--];elsenums1[end--] nums2[end2--];}while (end2 0)nums1[end--] nums2[end2--];
}
