力扣(LeetCode)88. 合并两个有序数组(C++)

朴素思想

朴素思想，开第三个数组，对 $nums1$ 和 $nums2$ 进行二路归并。

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指nums3
        while(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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度: $O(n+m)$ ， $n$ 是 $nums1$ 的长度， $m$ 是 $nums2$ 的长度，遍历所有数的时间复杂度是 $O(n+m)$ 。

空间复杂度: $O(n+m)$ ，$nums3$ 的空间复杂度是 $O(n+m)$ 。

逆序归并

由于 $nums1.size()=m+n$ ，思考倒着归并。设极端情况，$nums2$ 的元素全部大于 $nums1$ ，需要把 $nums2$ 接到 $nums1$ 后面，$nums1$ 前面 $m$ 个数是 $nums1$ 本身的数，后面 $n$ 个数是 $nums2$ 的数，$m+n=nums1.size()$ ，这种极端情况也可以容纳。那么正常归并时，如果选择 $nums1$ 的数，那么 $nums1$ 最后的数就可以被覆盖了，这种情况同样可以容纳。

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--];
    }
};
1
2
3
4
5
6
7
8
9
10
11

时间复杂度: $O(n+m)$ ， $n$ 是 $nums1$ 的长度， $m$ 是 $nums2$ 的长度，遍历所有数的时间复杂度是 $O(n+m)$ 。

空间复杂度: $O(1)$ ，只使用了常量级空间 。

致语

• 理解思路很重要！
• 欢迎读者在评论区留言，清墨看到就会回复的。

AC