C++高效查找两个有序数组的中位数

在算法问题中，查找两个有序数组的中位数是一个经典问题。本文将介绍如何使用C++高效地解决这个问题，并提供详细的代码示例和解题思路。

问题描述：

给定两个有序整数数组，长度均为n，要求找到这两个有序数组的中位数。

例如：

输入：a:[1,3,5] b:[2,4,6]

输出: 3.5

输入格式： a:[1,3,5] b:[2,4,6] （使用cin输入并以逗号分割）

解题思路：

我们可以利用归并排序的思想来解决这个问题。

合并数组： 首先，将两个有序数组合并成一个有序数组。2. 查找中位数： 根据合并后数组长度的奇偶性找到中位数。如果长度为奇数，则中位数为中间位置的元素；如果长度为偶数，则中位数为中间两个元素的平均值。

**C++代码实现：**cpp#include #include #include #include

using namespace std;

double findMedianSortedArrays(vector& nums1, vector& nums2) { int m = nums1.size(); int n = nums2.size(); vector merged;

int i = 0, j = 0;    while (i < m && j < n) {        if (nums1[i] < nums2[j]) {            merged.push_back(nums1[i]);            i++;        } else {            merged.push_back(nums2[j]);            j++;        }    }

while (i < m) {        merged.push_back(nums1[i]);        i++;    }

while (j < n) {        merged.push_back(nums2[j]);        j++;    }

int mergedSize = merged.size();    if (mergedSize % 2 == 1) {        return merged[mergedSize / 2];    } else {        int mid = mergedSize / 2;        return (merged[mid - 1] + merged[mid]) / 2.0;    }}

int main() { string input; getline(cin, input);

stringstream ss(input);    string temp;    vector<int> nums1, nums2;

while (getline(ss, temp, ',')) {        nums1.push_back(stoi(temp));    }

getline(cin, input);    stringstream ss2(input);    while (getline(ss2, temp, ',')) {        nums2.push_back(stoi(temp));    }

double median = findMedianSortedArrays(nums1, nums2);    cout << median << endl;

return 0;}

代码解析：

findMedianSortedArrays 函数接收两个有序数组 nums1 和 nums2 作为参数，返回它们的中位数。* 代码首先创建了一个新的数组 merged，用于存储合并后的有序数组。* 使用双指针 i 和 j 分别遍历数组 nums1 和 nums2，并将较小的元素添加到 merged 数组中，直到遍历完其中一个数组。* 将剩余的元素添加到 merged 数组中。* 根据 merged 数组的长度计算中位数并返回。

输入示例：

1,3,52,4,6

输出结果：

3.5

希望本文能够帮助你理解如何使用C++高效查找两个有序数组的中位数，并提升你的算法能力。