题目

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 寻找两个有序数组的中位数 - 图1。

可以假设 nums1 和 nums2 不会同时为空。

示例 1:

  1. nums1 = [1, 3]
  2. nums2 = [2]
  4. 中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

中位数是 (2 + 3)/2 = 2.5

方案一（合并，排序）

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    var nums = append(nums1, nums2...)
    sort.Ints(nums)

    var res float64
    if len(nums) % 2 == 1 {
        res = float64(nums[len(nums) / 2])
    } else {
        res = float64(nums[len(nums) / 2] + nums[len(nums) / 2 - 1]) / 2.0
    }

    return res
}
  • 时间复杂度 寻找两个有序数组的中位数 - 图2

    方案二（问题转换）

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m, n = len(nums1), len(nums2)

        mid = (m + n) // 2
        if (m + n) % 2 == 1:
            return self.getKth(nums1, 0, m - 1, nums2, 0, n - 1, mid + 1)
        else:
            return (self.getKth(nums1, 0, m - 1, nums2, 0, n - 1, mid) + self.getKth(nums1, 0, m - 1, nums2, 0, n - 1, mid + 1)) / 2

    def getKth(self, nums1, start1, end1, nums2, start2, end2, k):
        len1 = end1 - start1 + 1
        len2 = end2 - start2 + 1
        # 让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1

        if len1 > len2:
            return self.getKth(nums2, start2, end2, nums1, start1, end1, k)
        if len1 == 0:
            return nums2[start2 + k - 1]

        if k == 1:
            return min(nums1[start1], nums2[start2])

        i = int(start1 + min(len1, k / 2) - 1)
        j = int(start2 + min(len2, k / 2) - 1)

        if nums1[i] > nums2[j]:
            return self.getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1))
        else:
            return self.getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1))
  • 我们不妨用另一种思路，题目是求中位数，其实就是求第 k 小数的一种特殊情况

    原文

https://leetcode-cn.com/explore/learn/card/binary-search/215/more-practices-ii/859/
https://leetcode-cn.com/explore/learn/card/binary-search/215/more-practices-ii/859/