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

Difficulty
Hard
Tags
二分查找
URL
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
Star
给定两个大小分别为 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
  • 106 <= nums1[i], nums2[i] <= 106
通过次数620,199提交次数1,508,086

法 1 二分查找

参考 花花酱 LeetCode 4. Median of Two Sorted Arrays - 刷题找工作 EP102 - YouTube
思路
中位数理解：中位数是一堆数字中 按顺序看最中间的那个数字。是一堆数字，并不一定要求一个有序数组。也就是说，只要我能把这一堆数字均等分成两小堆nums1和nums2，且nums1中的最大值小于nums2中的最小值。那么中位数一定在这最大值 or 最小值中，要么直接就是一个，要么就是这俩的和。
 
现在对题目给的两个数组划分。具体划分大小是：
  • 如果这组数字个数和为偶数，那么均等划分。最后的结果为左边最大值与右边最小值的平均
  • 如果是奇数，那么让左边的一堆多一个数字。最后的结果为左边这一堆的最大值
假设 两组数的大小分别为n_1,n_2, 那么左边一堆数字个数为
现在开始划分，假设 第一组中选 m1 个数，那么第二组中就一定要选m2 = k - m1 个数。
notion imagenotion image
现在通过二分来选择 的值 ，
notion imagenotion image
题解
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        n1, n2 = len(nums1), len(nums2)
				# 保证了 nums1 数量少于 nums2， 这样nums2中一定会有数字被分到中位数左边
				# 即保证了 m2 >= 1 
        if n1 > n2:
            return self.findMedianSortedArrays(nums2, nums1)

        # 分割线左边需要有 k 个元素
        k = (n1 + n2 + 1) // 2
        # 在第一个数组中选择  多少个元素呢？
        l, r = 0, n1
        # 搜索区间是左闭又开的，所以下面 r = m1
        while l < r:
            m1 = l + (r - l) // 2
            m2 = k - m1
            # 当从 nums2 取m2 个数放在中位数左边
            # 此时左边最大的数 nums2[m2-1]需要小于右边最小的数nums1[m1]
            # 说明第一个数组中用的数量太少
            if nums1[m1] < nums2[m2-1]:
                l = m1 + 1
            else:
                r = m1
        # 在 nums1中选 m1 个元素， 在nums2 中选前 m2 个元素
        m1 = l
        m2 = k - l

        # 左半段的最大值
				#  
        c1 = max(-float("inf") if m1 <= 0 else nums1[m1-1],
                -float("inf") if m2 <= 0 else nums2[m2-1])

        if (n1 + n2) % 2 == 1:
            return c1

        # 右半段的最小值
        c2 = min(float("inf") if m1 >= n1 else nums1[m1],
                float("inf") if m2 >= n2 else nums2[m2])

        return (c1 + c2) / 2
注：首先理清楚思路，是用二分法来选择num1中有多少个数字要被划分到 左半块。其次明白 m1、m2的取值范围，这样才知道为什么最开始需要保证 num1中的数字少于 num2，且在二分的时候不会越界。最后会计算左半块的最大值，以及右半块的最小值。