.给定大小分别为m和n的升序排列数组,计算两个正序数组合并之后的中位数(保留一位小数)。例如,输入为1234和56749 时,输出结果为4.5。
时间: 2024-02-18 08:03:54 浏览: 73
可以使用归并排序的思想,将两个升序排列数组合并成一个有序数组,然后找到该有序数组的中位数即可。
具体思路如下:
1. 定义两个指针 i 和 j,分别指向两个数组的起始位置。
2. 比较两个指针所指的元素大小,将较小的元素放入新的数组中,同时将指针向后移动一位。
3. 如果其中一个数组的元素已经全部放入了新的数组中,那么直接将另一个数组的剩余元素依次放入新的数组中。
4. 如果新的数组的长度为偶数,那么中位数为中间两个数的平均值;如果新的数组的长度为奇数,那么中位数为中间的那个数。
以下是C++实现的代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
vector<int> merged(m + n); // 定义一个新的数组,用于存放合并后的有序数组
int i = 0, j = 0, k = 0; // i 和 j 分别指向 nums1 和 nums2 的起始位置,k 指向 merged 的起始位置
while (i < m && j < n) {
if (nums1[i] <= nums2[j]) {
merged[k] = nums1[i];
i++;
} else {
merged[k] = nums2[j];
j++;
}
k++;
}
// 如果 nums1 的元素已经全部放入 merged 中,那么将 nums2 的剩余元素依次放入 merged 中
while (j < n) {
merged[k] = nums2[j];
j++;
k++;
}
// 如果 nums2 的元素已经全部放入 merged 中,那么将 nums1 的剩余元素依次放入 merged 中
while (i < m) {
merged[k] = nums1[i];
i++;
k++;
}
// 根据 merged 的长度计算中位数
int len = m + n;
if (len % 2 == 0) {
return (merged[len/2 - 1] + merged[len/2]) / 2.0;
} else {
return merged[len/2];
}
}
int main() {
vector<int> nums1 = {1, 2, 3, 4};
vector<int> nums2 = {5, 6, 7, 4, 9};
double median = findMedianSortedArrays(nums1, nums2);
cout << "中位数为:" << median << endl;
return 0;
}
```
输出结果为:
```
中位数为:4.5
```
阅读全文
相关推荐







