力扣(LeetCode)88. 合并两个有序数组(C++)
朴素思想
朴素思想，开第三个数组，对 nums1nums1nums1 和 nums2nums2nums2 进行二路归并。
class Solution {
public:void merge(vector& nums1, int m, vector& nums2, int n) {vector nums3(m+n);int i =0,j = 0,k=0;//i指nums1,j指nums2,k指nums3while(i 时间复杂度: 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& nums1, int m, vector& 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
上一篇：【Spring】Bean生命周期