原题直达

1. 题目描述

给定两个大小分别为 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

-10⁶ <= nums1[i], nums2[i] <= 10⁶

2. 分析

核心思路：二分查找收缩

本题要求两个升序数组的中位数，先转化为求解通用问题：两个升序数组的第k小元素。

而后再根据元素个数奇偶，求解中位数。

3. 代码

3.1. 简单方案

func findKthElement(nums1 []int, nums2 []int, k int) int {
    if len(nums1) == 0 {
        return nums2[k-1]
    }
    if len(nums2) == 0 {
        return nums1[k-1]
    }
    if k == 1 {
        if nums1[0] < nums2[0] {
            return nums1[0]
        }
        return nums2[0]
    }
    if nums1[0] < nums2[0] {
        return findKthElement(nums1[1:], nums2, k-1)
    }
    return findKthElement(nums1, nums2[1:], k-1)
}

上述方案求解两个升序数组的第k小元素，基本思路是利用合并两个升序数组，找到第k小。时间复杂度O(m+n)。不符合题意。

3.2. 二分查找

func findKthElement(nums1 []int, nums2 []int, k int) int {
    m, n := len(nums1), len(nums2)
    // 边界条件：如果一个数组为空，直接在另一个数组中查找第 k 小元素
    if m == 0 {
        return nums2[k-1]
    }
    if n == 0 {
        return nums1[k-1]
    }
    // 边界条件：如果 k 为 1，直接返回两个数组中的最小值
    if k == 1 {
        if nums1[0] < nums2[0] {
            return nums1[0]
        }
        return nums2[0]
    }
    // 找到两个数组的第 k/2 个元素位置（注意索引偏移）
    // 如果数组长度不足 k/2，取最大长度
    idx1 := min(m, k>>1) - 1
    idx2 := min(n, k>>1) - 1
    // 比较两个数组的第 k/2 个元素
    if nums1[idx1] < nums2[idx2] {
        // nums1 收缩
        return findKthElement(nums1[idx1+1:], nums2, k-idx1-1)
    } else {
        // nums2 收缩
        return findKthElement(nums1, nums2[idx2+1:], k-idx2-1)
    }
}

func min(nums1, nums2 int) int {
    if nums1 < nums2 {
        return nums1
    }
    return nums2
}

最后，再根据奇偶性，求解中位数。

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    m, n := len(nums1), len(nums2)
    mid := (m + n) / 2
    if (m+n)&1 == 1 {
        // 奇数个，取中间值 注意索引偏移：[1,2,3] mid=1 中间值是第二个元素
        return float64(findKthElement(nums1, nums2, mid+1))
    }
    // 偶数个，取中间两个值
    return float64(findKthElement(nums1, nums2, mid)+findKthElement(nums1, nums2, mid+1)) / 2
}