寻找两个正序数组的中位数

题解思路

方法：二分查找（$O(\log (m+n))$）

我们不需要真的合并 nums1 和 nums2，而是通过 二分查找 在 较短的数组上 进行分割，确定中位数。

1. 目标

我们要找到 合并后数组的中位数：

• 若总长度是奇数，中位数是第 (m+n)//2 + 1 个元素。
• 若总长度是偶数，中位数是 第 (m+n)//2 和 (m+n)//2 + 1 个元素的平均值。

2. 二分查找的分割策略

我们 始终在较短的数组 nums1 上二分（保证 m <= n），选择一个分割点 i，使得：

nums1[0:i] 和 nums2[0:j] 在合并后构成中位数的左半部分
nums1[i:m] 和 nums2[j:n] 在合并后构成中位数的右半部分

其中 j = (m + n + 1) / 2 - i 确保左侧部分的长度接近于右侧部分。

3. 二分调整

• 若 nums1[i] < nums2[j-1]，说明 nums1 的分割太靠左，需要 i 右移。
• 若 nums1[i-1] > nums2[j]，说明 nums1 的分割太靠右，需要 i 左移。

最终，找到合适的 i 和 j 后，就可以计算 中位数。

代码实现

Python 代码

import sys

def findMedianSortedArrays(nums1, nums2):
    if len(nums1) > len(nums2):  # 确保 nums1 是较短的数组
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    left, right = 0, m
    half_len = (m + n + 1) // 2

    while left <= right:
        i = (left + right) // 2
        j = half_len - i  # 确保左侧部分长度接近右侧部分

        if i < m and nums1[i] < nums2[j - 1]:  # i 太小，右移
            left = i + 1
        elif i > 0 and nums1[i - 1] > nums2[j]:  # i 太大，左移
            right = i - 1
        else:  # 找到了合适的 i
            max_of_left = max(nums1[i - 1] if i > 0 else float('-inf'),
                              nums2[j - 1] if j > 0 else float('-inf'))
            if (m + n) % 2 == 1:
                return round(max_of_left, 5)  # 奇数长度，直接返回

            min_of_right = min(nums1[i] if i < m else float('inf'),
                               nums2[j] if j < n else float('inf'))
            return round((max_of_left + min_of_right) / 2, 5)  # 偶数长度，返回平均值

# 读取输入
m = int(sys.stdin.readline().strip())
nums1 = list(map(int, sys.stdin.readline().split())) if m > 0 else []
n = int(sys.stdin.readline().strip())
nums2 = list(map(int, sys.stdin.readline().split())) if n > 0 else []

# 输出结果
median = findMedianSortedArrays(nums1, nums2)
print(f"{median:.5f}")

Java 代码

import java.util.Scanner;

public class Main {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length, n = nums2.length;
        int left = 0, right = m, halfLen = (m + n + 1) / 2;

        while (left <= right) {
            int i = (left + right) / 2;
            int j = halfLen - i;

            if (i < m && nums1[i] < nums2[j - 1]) {
                left = i + 1;
            } else if (i > 0 && nums1[i - 1] > nums2[j]) {
                right = i - 1;
            } else {
                int maxOfLeft = Math.max(i > 0 ? nums1[i - 1] : Integer.MIN_VALUE,
                                         j > 0 ? nums2[j - 1] : Integer.MIN_VALUE);
                if ((m + n) % 2 == 1) {
                    return maxOfLeft;
                }
                int minOfRight = Math.min(i < m ? nums1[i] : Integer.MAX_VALUE,
                                          j < n ? nums2[j] : Integer.MAX_VALUE);
                return (maxOfLeft + minOfRight) / 2.0;
            }
        }
        return 0.0;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int[] nums1 = new int[m];
        for (int i = 0; i < m; i++) nums1[i] = scanner.nextInt();
        int n = scanner.nextInt();
        int[] nums2 = new int[n];
        for (int i = 0; i < n; i++) nums2[i] = scanner.nextInt();

        System.out.printf("%.5f\n", findMedianSortedArrays(nums1, nums2));
    }
}

c++代码

#include <bits/stdc++.h>
using namespace std;

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    if (nums1.size() > nums2.size()) {
        return findMedianSortedArrays(nums2, nums1); // 确保 nums1 是较短的数组
    }

    int m = nums1.size(), n = nums2.size();
    int left = 0, right = m, half_len = (m + n + 1) / 2;

    while (left <= right) {
        int i = (left + right) / 2;
        int j = half_len - i;

        if (i < m && nums1[i] < nums2[j - 1]) {
            left = i + 1;  // i 太小，右移
        } else if (i > 0 && nums1[i - 1] > nums2[j]) {
            right = i - 1; // i 太大，左移
        } else {
            // 找到合适的 i
            int max_of_left = max(i > 0 ? nums1[i - 1] : INT_MIN,
                                  j > 0 ? nums2[j - 1] : INT_MIN);

            if ((m + n) % 2 == 1) {
                return max_of_left; // 奇数长度，返回中位数
            }

            int min_of_right = min(i < m ? nums1[i] : INT_MAX,
                                   j < n ? nums2[j] : INT_MAX);

            return (max_of_left + min_of_right) / 2.0; // 偶数长度，返回均值
        }
    }
    return 0.0; // 兜底逻辑，实际不会执行到这里
}

int main() {
    int m, n;
    cin >> m;
    vector<int> nums1(m);
    for (int i = 0; i < m; i++) {
        cin >> nums1[i];
    }

    cin >> n;
    vector<int> nums2(n);
    for (int i = 0; i < n; i++) {
        cin >> nums2[i];
    }

    cout << fixed << setprecision(5) << findMedianSortedArrays(nums1, nums2) << endl;
    return 0;
}

Leetcode 68.寻找两个正序数组的中位数-原题链接

题目内容

给定两个大小分别为 $m$和 $n$的正序（从小到大）数组 $nums1$和 $nums2$。请你找出并返回这两个正序数组的中位数。

算法的时间复杂度应该为 $O(log\ (m+n))$。

输入描述

• 第一行输入一个整数 m，表示数组 nums1 的长度。
• 第二行输入 m 个整数，表示数组 nums1。
• 第三行输入一个整数 n，表示数组 nums2 的长度。
• 第四行输入 n 个整数，表示数组 nums2。

输出描述

输出一个浮点数，表示两个数组的 中位数，精确到 5 位小数。

样例1

输入

2
1 3
1
2

输出

2.00000

说明

合并数组 = $[1,2,3]$ ，中位数 $2$

样例2

输入

2
1 2
2
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$
• $-10^6 <= nums1[i], nums2[i] <= 10^6$