仅供自己学习

思路：

1. 因为num1的空间能容纳num1和num2的内容，所以第一种方法就是可以把num2的数全加进num1中然后在sort即可。 相当于调用快排时间复杂度为O（（m+n）log（m+n）），空间复杂度O（1）
2. 第二种方法是创建一个数组，然后比较num1和num2的大小放入新数组，最后再把新数组赋给num1. 时间复杂度O（m+n），空间复杂度O（m+n）

上述方法比较简单就不加代码了。

3. 第三种方法就是原地算法，因为nums1的空间足够大，那么我们从最后开始向前遍历，先找最大值让入空余的空间，这样就能存入num1还不会覆盖元素。先比较nums1和nums2的最后一个元素 谁更大，然后放入nums1的最后一个位置，谁放谁的指针就要向前移动。如果nums1和nums2的指针指向的位置为-1，那说明这个数组已经遍历完了，后面的全让没有达到-1的数组填满即可。循环结束的条件也是两个指针都为-1.

代码：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int n2=n-1,n1=m-1;
        int i=0;
        while(n1>=0||n2>=0){
           if(n1==-1) nums1[m+n-1-i]=nums2[n2--];
           else if(n2==-1) nums1[m+n-1-i]=nums1[n1--];
           else if(nums1[n1]>nums2[n2]) nums1[m+n-1-i]=nums1[n1--];
           else nums1[m+n-1-i]=nums2[n2--];
           i++;
        }
    }
};