给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (m+n)) 。 示例 1: 输入:nums1 = [1,3], nums2 = [2] 输出:2.00000 解释:合并数组 = [1,2,3] ,中位数 2 示例 2: 输入:nums1 = [1,2], nums2 = [3,4] 输出:2.50000 解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5 提示: nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -106 <= nums1[i], nums2[i] <= 106
时间: 2023-03-31 19:00:40 浏览: 118
这是一个计算问题,我可以回答。根据题目要求,我们需要将两个数组合并成一个有序数组,然后找到中位数。可以使用归并排序的思想,将两个数组合并成一个有序数组,然后根据数组长度的奇偶性,找到中间位置的数或者中间两个数的平均数作为中位数。具体实现可以参考以下代码:
```
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
int len = m + n;
int left = -1, right = -1;
int i = , j = ;
for (int k = ; k <= len / 2; k++) {
left = right;
if (i < m && (j >= n || nums1[i] < nums2[j])) {
right = nums1[i++];
} else {
right = nums2[j++];
}
}
if (len % 2 == ) {
return (left + right) / 2.;
} else {
return right;
}
}
};
```
阅读全文