朴素思想
朴素思想，开第三个数组，对 nums1nums1nums1 和 nums2nums2nums2 进行二路归并。
class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {vector<int> nums3(m+n);int i =0,j = 0,k=0;//i指nums1,j指nums2,k指nums3while(i<m&&j<n)if(nums1[i]<=nums2[j]) nums3[k++] = nums1[i++];else nums3[k++] = nums2[j++];while(i<m) nums3[k++] = nums1[i++];while(j<n) nums3[k++] = nums2[j++];nums1 = nums3;}
};
时间复杂度: O(n+m)O(n+m)O(n+m) ， nnn 是 nums1nums1nums1 的长度， mmm 是 nums2nums2nums2 的长度，遍历所有数的时间复杂度是 O(n+m)O(n+m)O(n+m) 。
空间复杂度: O(n+m)O(n+m)O(n+m) ，nums3nums3nums3 的空间复杂度是 O(n+m)O(n+m)O(n+m) 。
逆序归并
由于 nums1.size()=m+nnums1.size()=m+nnums1.size()=m+n ，思考倒着归并。设极端情况，nums2nums2nums2 的元素全部大于 nums1nums1nums1 ，需要把 nums2nums2nums2 接到 nums1nums1nums1 后面，nums1nums1nums1 前面 mmm 个数是 nums1nums1nums1 本身的数，后面 nnn 个数是 nums2nums2nums2 的数，m+n=nums1.size()m+n=nums1.size()m+n=nums1.size() ，这种极端情况也可以容纳。那么正常归并时，如果选择 nums1nums1nums1 的数，那么 nums1nums1nums1 最后的数就可以被覆盖了，这种情况同样可以容纳。
class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int i =m-1,j = n-1,k=m+n-1;//i指nums1,j指nums2,k指nums1末尾while(i>=0&&j>=0)if(nums1[i]>nums2[j]) nums1[k--] = nums1[i--];else nums1[k--] = nums2[j--];while(i>=0) nums1[k--] = nums1[i--];while(j>=0) nums1[k--] = nums2[j--];}
};
时间复杂度: O(n+m)O(n+m)O(n+m) ， nnn 是 nums1nums1nums1 的长度， mmm 是 nums2nums2nums2 的长度，遍历所有数的时间复杂度是 O(n+m)O(n+m)O(n+m) 。
空间复杂度: O(1)O(1)O(1) ，只使用了常量级空间 。
致语
- 理解思路很重要！
- 欢迎读者在评论区留言，清墨看到就会回复的。
AC
