# 0088. 合并两个有序数组
### 题目地址（88. 合并两个有序数组）
### 题目描述
```
给定两个有序整数数组 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的末尾, 然后排序`
具体代码：
```js
// 这种解法连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 过程。merge 的过程`可以`是先比较两个数组的**头元素**，然后将较小的推到最终的数组中，并将其从原数组中出队列。不断循环直到两个数组都为空。
具体代码如下：
```js
// 将nums1 和 nums2 合并
function merge(nums1, nums2) {
let ret = [];
let i = (j = 0);
while (i < nums1.length || j < nums2.length) {
if (i === nums1.length) {
ret.push(nums2[j]);
j++;
continue;
}
if (j === nums2.length) {
ret.push(nums1[i]);
i++;
continue;
}
const a = nums1[i];
const b = nums2[j];
if (a > b) {
ret.push(nums2[j]);
j++;
} else {
ret.push(nums1[i]);
i++;
}
}
return ret;
}
```
但是 merge sort 很多时候，合并的时候我们通常是新建一个数组，但是这道题目要求的是`原地修改`.这就和 merge sort 的 merge 过程有点不同。这里要求原地修改。如果使用类似上面的方法，如果采用从头开始遍历，**需要将 nums1 的前 m 个数组放到另一个数组中避免写指针写入的干扰**。 这样空间复杂度就是 $O(m)$。其实我们能只要从**后往前比较，并从后往前插入即可。**
我们需要三个指针：
1. 写指针 current， 用于记录当前填补到那个位置了
2. m 用于记录 nums1 数组处理到哪个元素了
3. n 用于记录 nums2 数组处理到哪个元素了
如图所示：
* 灰色代表 num2 数组已经处理过的元素
* 红色代表当前正在进行比较的元素
* 绿色代表已经就位的元素
  
### 关键点解析
* 从后往前比较，并从后往前插入，这样可避免写指针影响，同时将空间复杂度降低到 $O(1)$
### 代码
代码支持：Python3, C++, Java, JavaScript
JavaSCript Code:
```js
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:
```
class Solution {
public:
void merge(vector& nums1, int m, vector& 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:
```java
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:
```python
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.
"""
pos = m + n - 1
while m > 0 and n > 0:
if nums1[m - 1] < nums2[n - 1]:
nums1[pos] = nums2[n - 1]
n -= 1
else:
nums1[pos] = nums1[m - 1]
m -= 1
pos -= 1
while n > 0:
nums1[pos] = nums2[n - 1]
n -= 1
pos -= 1
```
**复杂度分析**
* 时间复杂度：$O(M + N)$
* 空间复杂度：$O(1)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。
大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
