一、题述

给你两个有序整数数组 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]

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[i] <= 109

二、题解

1、直接法

我们可以直接把两个数组拼接起来，然后用sort函数对整合后的数组进行一个排序。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int i=0;i!=n;i++){
            nums1[m+i]=nums2[i]; //对两个数组进行拼接
        }
        sort(nums1.begin(),nums1.end()); //STL排序
    }
};

复杂度分析

• 时间复杂度：O((m+n)\log(m+n))O((m+n)log(m+n))。
  快速排序、序列长度为 m+nm+n。

• 空间复杂度：O(\log(m+n))O(log(m+n))。
  快速排序、序列长度为 m+nm+n。

2、双指针

由于题目中给的两个数组序列是已经排序好的，所以我们可以用双指针的办法，对两数组进行按序组合。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = 0, p2 = 0; //定义两个空指针
        int sorted[m + n];
        int temp;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                temp = nums2[p2++];
            } else if (p2 == n) {
                temp = nums1[p1++]; //当有一方到头时直接将后半段拼接
            } else if (nums1[p1] < nums2[p2]) {
                temp = nums1[p1++];
            } else {
                temp = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = temp;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i]; //数组赋值
        }
    }
};

复杂度分析

• 时间复杂度：O(m+n)。
  指针移动单调递增，最多移动 m+n 次，因此时间复杂度为 O(m+n)。

• 空间复杂度：O(m+n)。
  建立长度为 m+n 的中间数组。

3、逆向双指针（Leetcode解答）

2中，为防止 nums1 中的变量被覆盖，所以我们采用新建一个临时变量的方法以规避这一问题。但同时的，我们也可以采用逆向的方法，可以将指针设置为从后向前遍历，每次取两者之中的较大者放进  nums1​ 的最后面，从后向前覆盖。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = nums1.size();
        while (n > 0) {
            if (m > 0 && nums1[m-1] > nums2[n-1]) {
                nums1[--i] = nums1[--m]; 
            }else{
                nums1[--i] = nums2[--n];  //先自减后操作
            }
        }
    }
};

复杂度分析

• 时间复杂度：O(m+n)。
  指针移动单调递减，最多移动 m+n 次，因此时间复杂度为 O(m+n)。

• 空间复杂度：O(1)。
  直接对数组 nums1 原地修改，不需要额外空间。