题目描述

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

算法1

(双指针) $O(n)$

这道题依然可以用双指针来做，非常类似于归并排序中将两个数组合并的那一步，需要开辟一个新的变量存放合并后的数组，最后再将数组传回nums1中即可

C++ 代码

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> n3(m+n);
        int i=0,j=0,k=0;
        while(i<m&&j<n){
            if(nums1[i]<nums2[j]) n3[k++]=nums1[i++];
            else n3[k++]=nums2[j++];
        }
        while(i<m) n3[k++]=nums1[i++];
        while(j<n) n3[k++]=nums2[j++];
        nums1 = n3;
    }
};

在上面的仿归并算法中，需要临时一个构建一个数组，空间复杂度不是常数，通过观察题，没有充分利用题目所给的条件，nums1已经开够了足够大，如果直接在nums1上合并，便不需要额外的空间，而如果从前往后合并，要么会覆盖元素得到错误结果，要么元素整体后移导致时间复杂度上升n^2，再通过观察，如果从后往前合并的方式，则不会覆盖，也不会时间复杂度退化，是理想的解法，时间O(n)，空间常数

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p=m-1,q=n-1,cur=m+n-1;
        while(p>=0&&q>=0)
            nums1[cur--]=nums1[p]>nums2[q]?nums1[p--]:nums2[q--];
        while(q>=0)
            nums1[cur--] = nums2[q--];
    }
};