题目描述
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example1:
nums1 = [1, 3] nums2 = [2]
The median is 2.0
Example2:
nums1 = [1, 2] nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
解题思路
- 时间复杂度不满足！！！
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
const auto len1 = nums1.size();
const auto len2 = nums2.size();
nums1.reserve(len1 + len2);
for(auto num : nums2){
nums1.push_back(num);
}
nums2.resize(len1 + len2);
merge(nums1.begin(), nums1.begin() + len1, nums1.begin() + len1, nums1.end(), nums2.begin());
const int n = nums2.size() / 2;
if(nums2.size() % 2 == 0){
return (double)(nums2[n] + nums2[n - 1]) / 2;
}
return (double)nums2[n];
}
};
