題目描述
給定兩個大小為 m 和 n 的有序數(shù)組 nums1 和 nums2厨疙。
請你找出這兩個有序數(shù)組的中位數(shù)饲握，并且要求算法的時間復(fù)雜度為 O(log(m + n))砂豌。
你可以假設(shè) nums1 和 nums2 不會同時為空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
則中位數(shù)是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
則中位數(shù)是 (2 + 3)/2 = 2.5
思考
這題難度標記為困難阁谆，其實不要被難度標記嚇到了
讀完題目會發(fā)現(xiàn)還是比較簡單的宁赤，思路很清晰
把兩個有序數(shù)組合成一個有序數(shù)組纹坐，然后取中位數(shù)就可以了记某，而且時間復(fù)雜度也不高只需要一次遍歷
也可以在合并遍歷的時候就拿到中位數(shù)
代碼
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> nums;
int i = 0;
int j = 0;
for (; i < nums1.size(); i++) {
bool addI = false;
for (; j < nums2.size(); j++) {
if (nums2[j] > nums1[i]) {
nums.push_back(nums1[i]);
addI = true;
break;
}
nums.push_back(nums2[j]);
}
if (!addI) {
nums.push_back(nums1[i]);
}
}
for (; j < nums2.size(); j++) {
nums.push_back(nums2[j]);
}
if (nums.size() % 2 == 0) {
return 1.0 * (nums[nums.size() / 2] + nums[nums.size() / 2 - 1]) / 2.0;
} else {
return nums[nums.size() / 2];
}
}
};
