4. 两个排序数组的中位数

￡神魔★判官ぃ 2022-05-21 09:20 159阅读 0赞

[题目描述][Link 1] [提示帮助][Link 2] [提交记录][Link 3] 社区讨论 [阅读解答][Link 4]

[随机一题][Link 5]

--------------------

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

示例 1:

nums1 = [1, 3]
    nums2 = [2]
    
    中位数是 2.0

示例 2:

nums1 = [1, 2]
    nums2 = [3, 4]
    
    中位数是 (2 + 3)/2 = 2.5

class Solution {public:    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int m = nums1.size();        int n = nums2.size();        if (nums1.empty()) {            if (n%2 != 0)                return 1.0*nums2[n/2];            return (nums2[n/2]+nums2[n/2-1])/2.0;        }        if (nums2.empty()) {            if (m%2 != 0)                return 1.0*nums1[m/2];            return (nums1[m/2]+nums1[m/2-1])/2.0;        }        int i = 0;        int j = 0;        vector<int> ans;        while (i < m && j < n) {            if (nums1[i] <= nums2[j]) {                ans.push_back(nums1[i]);                i++;            } else {                ans.push_back(nums2[j]);                j++;            }        }        if (i < m) {            for (; i < m; i++)                ans.push_back(nums1[i]);        } else if (j < n) {            for (; j < n; j++)                ans.push_back(nums2[j]);        }        int len = ans.size();        if (len%2 != 0)            return 1.0*ans[len/2];        return (ans[len/2]+ans[len/2-1])/2.0;    }
    };

[Link 1]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/description/
[Link 2]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/hints/
[Link 3]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/submissions/
[Link 4]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/
[Link 5]: https://leetcode-cn.com/problems/random-one-question/