求解两个升序序列的中位数cpp

在C++中，求解两个升序序列的中位数可以分为以下步骤：

1. **合并排序**：首先将这两个升序序列合并成一个新的有序数组。你可以使用双指针法，一个指向第一个序列的开始，另一个指向第二个序列的开始，每次比较并选择较小的那个元素添加到结果数组中，直到其中一个序列遍历完。

int merge(int arr1[], int m, int arr2[], int n) {
    int i = 0, j = 0, k = 0;
    while (i < m && j < n) {
        if (arr1[i] <= arr2[j]) {
            arr[k++] = arr1[i++];
        } else {
            arr[k++] = arr2[j++];
        }
    }

    // 将剩余未处理的部分添加到结果数组
    while (i < m) {
        arr[k++] = arr1[i++];
    }
    while (j < n) {
        arr[k++] = arr2[j++];
    }
    return k;
}

2. **查找中位数**：合并后的数组已经是有序的，对于长度为奇数的数组，中位数就是中间那个元素；对于长度为偶数的数组，中位数则是中间两个元素的平均值。

double findMedian(int merged[], int size) {
    if (size % 2 == 0) {
        return (merged[size / 2 - 1] + merged[size / 2]) * 0.5; // 对于偶数长度，取中间两个数的平均
    } else {
        return merged[size / 2]; // 对于奇数长度，直接返回中间的那个数
    }
}

完整的函数示例：

double medianSortedArrays(int* nums1, int m, int* nums2, int n) {
    int total_size = m + n;
    int* merged = new int[total_size];
    std::merge(nums1, nums1 + m, nums2, nums2 + n, merged);
    
    delete[] merged;
    
    return findMedian(merged, total_size);
}