合并两个有序数组-88e

未分类
136 词

效率更高的方法是使用双指针，时间复杂度为 O(m+n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int sum = m+n-1;
        int i = m-1;
        int j = n-1;
        //当两数组均含有未合并元素时
        while(i >= 0 && j >= 0){
            if(nums1[i] >= nums2[j]) nums1[sum] = nums1[i], sum--, i--;
            else nums1[sum] = nums2[j], sum--, j--;
        }
        //若nums2还有未合并元素，则全部加入结果
        while(j >= 0) nums1[sum] = nums2[j], sum--, j--;
    }
};

视频链接：https://www.bilibili.com/video/BV1AY4y1B7rP/?spm_id_from=333.337.search-card.all.click&vd_source=8a00a24977de92674a7b9aebcdcb67f9

力扣：https://leetcode.cn/problems/merge-sorted-array/description/

留言