一、问题
给定两个大小分别为 m
和 n
的排序数组 nums1
和 nums2
,要求你在 O(log(m+n)) 的时间复杂度内找出这两个数组的中位数。
二、思路
时间复杂度O(log(n))代表随着操作数增加,剩余操作数递减,如二分法。
首先要建模,对这个问题有一个具体的表达,建模的方式决定了解决问题的难易程度。在这里我就是因为错误建模走错了方向,需要分类讨论的情况越来越多,问题越来越复杂。
首先看到时间复杂度的要求,表明应该与二分法相关,如何把这个问题与二分挂钩呢。这个问题要找两个数组合并后的中位数,实际上,合并后数组的中位数就是将数组分成两半,中间的数就是中位数。换句话说要将这个数组分成两个大小相等的数组,其中一个数组中的最大元素小于另一个数组的最小元素,如下图所示。图片来自4. 寻找两个正序数组的中位数 - 力扣(LeetCode)
可见,问题的关键在于找到这样一个分割线,使得左侧的最大值小于右侧的最小值。
三、题解
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 二分查找
m = len(nums1)
n = len(nums2)
if m > n:
nums1,nums2 = nums2,nums1
m,n = len(nums1),len(nums2)
# 从数组1中取line1个数,从数组2中取line2个数组成left,其余是right
line1 = 0
infinty = 2**40
while line1 <= m:
line2 = (m+n+1)//2 - line1
maxleft1 = nums1[line1-1] if line1 > 0 else -infinty
maxleft2 = nums2[line2-1] if line2 > 0 else -infinty
maxleft = max(maxleft1,maxleft2)
minright1 = nums1[line1] if line1 < m else infinty
minright2 = nums2[line2] if line2 < n else infinty
minright = min(minright1,minright2)
if maxleft <= minright:
return maxleft if (m+n)%2 == 1 else (maxleft+minright)/2
else:
line1 += 1