# 0088. 合并两个有序数组

### 题目地址（88. 合并两个有序数组）

<https://leetcode-cn.com/problems/merge-sorted-array/>

### 题目描述

```
给定两个有序整数数组 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 数组已经处理过的元素
* 红色代表当前正在进行比较的元素
* 绿色代表已经就位的元素

![88.merge-sorted-array-1](https://p.ipic.vip/vkiwwv.jpg) ![88.merge-sorted-array-2](https://p.ipic.vip/uaep0y.jpg) ![88.merge-sorted-array-3](https://p.ipic.vip/5x29zr.jpg)

### 关键点解析

* 从后往前比较，并从后往前插入，这样可避免写指针影响，同时将空间复杂度降低到 $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<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:

```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 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。

大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

![](https://p.ipic.vip/sqb4n7.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/88.merge-sorted-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.