0088. 合并两个有序数组 · ttttt

# 0088. 合并两个有序数组 ## 题目地址（88. 合并两个有序数组） <https://leetcode-cn.com/problems/merge-sorted-array/> ## 题目描述 ``` <pre class="calibre18">``` 给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。示例: 输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6] ``` ``` ## 公司 - 阿里 - 腾讯 - 百度 - 字节 - loomberg - facebook - microsoft ## 前置知识 - 归并排序 ## 思路符合直觉的做法是`将nums2插到num1的末尾, 然后排序` 具体代码： ``` <pre class="calibre18">``` // 这种解法连m都用不到 // 这显然不是出题人的意思 if (n === 0) return; let current2 = 0; for (let i = nums1.length - 1; i >= nums1.length - n; i--) { nums1[i] = nums2[current2++]; } nums1.sort((a, b) => a - b); // 当然你可以自己写排序，这里懒得写了，因为已经偏离了题目本身 ``` ``` 这道题目其实和基本排序算法中的`merge sort`非常像，但是 merge sort 很多时候，合并的时候我们通常是新建一个数组，这样就很简单。但是这道题目要求的是`原地修改`. 这就和 merge sort 的 merge 过程有点不同，我们先来回顾一下 merge sort 的 merge 过程。 merge 的过程`可以`是先比较两个数组的头元素，然后将较小的推到最终的数组中，并将其从原数组中出队列。循环直到两个数组都为空。具体代码如下： ``` <pre class="calibre18">``` // 将nums1 和 nums2 合并 function merge(nums1, nums2) { let ret = []; while (nums1.length || nums2.length) { // 为了方便大家理解，这里代码有点赘余 if (nums1.length === 0) { ret.push(nums2.shift()); continue; } if (nums2.length === 0) { ret.push(nums1.shift()); continue; } const a = nums1[0]; const b = nums2[0]; if (a > b) { ret.push(nums2.shift()); } else { ret.push(nums1.shift()); } } return ret; } ``` ``` 这里要求原地修改，其实我们能只要从后往前比较，并从后往前插入即可。我们需要三个指针： 1. current 用于记录当前填补到那个位置了 2. m 用于记录 nums1 数组处理到哪个元素了 3. n 用于记录 nums2 数组处理到哪个元素了如图所示： - 灰色代表 num2 数组已经处理过的元素 - 红色代表当前正在进行比较的元素 - 绿色代表已经就位的元素 ![](https://img.kancloud.cn/15/d8/15d82e9142c52e3429091e20b7d0f2b4_612x829.jpg)![](https://img.kancloud.cn/98/30/9830fa745d6a507656cac3ddff51bee7_499x309.jpg)![](https://img.kancloud.cn/24/24/242422fbe043034cd0dc76f575536767_442x259.jpg) ## 关键点解析 - 从后往前比较，并从后往前插入 ## 代码代码支持：Python3, C++, Java, JavaScript JavaSCript Code: ``` <pre class="calibre18">``` var merge = function (nums1, m, nums2, n) { // 设置一个指针，指针初始化指向nums1的末尾（根据#62，应该是index为 m+n-1 的位置，因为nums1的长度有可能更长） // 然后不断左移指针更新元素 let current = m + n - 1; while (current >= 0) { // 没必要继续了 if (n === 0) return; // 为了方便大家理解，这里代码有点赘余 if (m < 1) { nums1[current--] = nums2[--n]; continue; } if (n < 1) { nums1[current--] = nums1[--m]; continue; } // 取大的填充 nums1的末尾 // 然后更新 m 或者 n if (nums1[m - 1] > nums2[n - 1]) { nums1[current--] = nums1[--m]; } else { nums1[current--] = nums2[--n]; } } }; ``` ``` C++ code: ``` <pre class="calibre18">``` class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int current = m + n - 1; while (current >= 0) { if (n == 0) return; if (m < 1) { nums1[current--] = nums2[--n]; continue; } if (n < 1) { nums1[current--] = nums1[--m]; continue; } if (nums1[m - 1] > nums2[n - 1]) nums1[current--] = nums1[--m]; else nums1[current--] = nums2[--n]; } } }; ``` ``` Java Code: ``` <pre class="calibre18">``` class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int i=m-1, j=n-1, k=m+n-1; // 合并 while(i>=0 && j>=0) { if(nums1[i] > nums2[j]) { nums1[k--] = nums1[i--]; } else { nums1[k--] = nums2[j--]; } } // 合并剩余的nums2 while(j>=0) { nums1[k--] = nums2[j--]; } } } ``` ``` Python Code: ``` <pre class="calibre18">``` class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ # 整体思路相似，只不过没有使用 current 指针记录当前填补位置 while m > 0 and n > 0: if nums1[m-1] <= nums2[n-1]: nums1[m+n-1] = nums2[n-1] n -= 1 else: nums1[m+n-1] = nums1[m-1] m -=1 """ 由于没有使用 current，第一步比较结束后有两种情况: 1. 指针 m>0，n=0，此时不需要做任何处理 2. 指针 n>0，m=0，此时需要将 nums2 指针左侧元素全部拷贝到 nums1 的前 n 位 """ if n > 0: nums1[:n] = nums2[:n] ``` ``` **复杂度分析** - 时间复杂度：O(M+N)O(M + N)O(M+N) - 空间复杂度：O(1)O(1)O(1) 欢迎关注我的公众号《脑洞前端》获取更多更新鲜的 LeetCode 题解 ![](https://img.kancloud.cn/77/1d/771d6f53e2a51febbcb6fa97f2899ac3_1586x578.jpg)