商丘网站制作推广,成都网站设计 创新互联,程序员网站需要多少钱,品牌网站建设策划方案【美团面试题】合并两个有序数组题目描述给你两个有序整数数组 nums1 和 nums2#xff0c;请你将 nums2 合并到 nums1 中#xff0c;使 nums1 成为一个有序数组划重点初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 有足够的空间#xff08;空间大小大于…【美团面试题】合并两个有序数组题目描述给你两个有序整数数组 nums1 和 nums2请你将 nums2 合并到 nums1 中使 nums1 成为一个有序数组划重点初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 有足够的空间空间大小大于或等于 m n来保存 nums2 中的元素示例示例 1:输入
nums1 [1,2,3,0,0,0], m 3
nums2 [2,5,6], n 3输出[1,2,2,3,5,6]
提示-10^9 nums1[i], nums2[i] 10^9
nums1.length m n
nums2.length n
解题思路两个数组分别有序且最终要输出的是数组一解法如下解法解法一 暴力法将数组nums2中的元素全部添加到nums1中对nums1做排序解法二倒插法已知条件Nums1 的剩余空间刚好可以存放nums2的元素nums1和nums2都是有序的。已知两个数组的元素个数通过分析一直条件我们可以发现nums1存在一定的后置空间因此我们可以考虑通过对两个数组的末位元素进行对比然后从后往前插入到nums1中的方法。所以我们可以用三个指针P0,P1,P2来遍历数组P0 记录nums1的新元素位置P1 记录nums1原数组的元素位置P2 记录nums2原数组的元素位置设置遍历条件 (p1 0 p2 0)比较指针指向的元素大小将较大的元素放入指针P0的位置同时移动P0和较大元素的指针。当遍历条件为 false时 存在三种情况P1 0 P2 0 数组都遍历完了P1 0 P2 0 Nums2没有遍历完P1 0 P2 0 Nums1没有遍历完当结果出现1和3时nums1恰好是合并排序的最终结果当出现结果2时说明nums2中还有剩余元素所以继续移动指针P1将nums2剩余元素插入到nums1中就行代码实现 public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 m - 1;int p2 n - 1;int p0 m n - 1;while (p1 0 p2 0) {if (nums1[p1] nums2[p2]) {nums1[p0] nums1[p1];p1--;} else {nums1[p0] nums2[p2];p2--;}p0--;}// 处理 nums2 没有遍历完的情况while (p2 0) {nums1[p0--] nums2[p2--];}}
复杂度分析时间复杂度O(n m)空间复杂度O(1)
