難度：困難 ??????類型： 數(shù)組
給定兩個大小為 m 和 n 的有序數(shù)組 nums1 和 nums2。
請你找出這兩個有序數(shù)組的中位數(shù)莫秆，并且要求算法的時間復雜度為 O(log(m + n))娶眷。
你可以假設 nums1 和 nums2 不會同時為空档址。
示例1
nums1 = [1, 3]
nums2 = [2]
則中位數(shù)是 2.0
示例2
nums1 = [1, 2]
nums2 = [3, 4]
則中位數(shù)是 (2 + 3)/2 = 2.5
解題思路
將問題廣義化為尋找兩個數(shù)組中第K小的數(shù)
設兩個數(shù)組num1, num2的長度分別為l1, l2
當l1+l2為奇數(shù)年叮，k=(l1+l2)//2
當l1+l2為偶數(shù)锉试，分別找到第(l1+l2)//2-1和第(l1+l2)//2個數(shù)求均值
如何找第k個數(shù)瘸洛？
二分法揍移，每次將兩個數(shù)組分成兩半，中位數(shù)分別為m1和m2,中位數(shù)的下標分別為i1和i2
若i1+i2<k反肋，即第k個數(shù)一定不在某個數(shù)組的前半部分那伐，當m1>m2時，第k個數(shù)一定不在nums2的前半部分石蔗，下一次搜索改為在nums1和nums2的后半部分里尋找第k-i2-1個數(shù)罕邀；當m1<=m2時,同理，問題變?yōu)樵趎ums1的后半部分和nums2里尋找第k-i1-1個數(shù)
若i1+i2>=k养距，即第k個數(shù)一定不在某個數(shù)組的后半部分诉探，當m1>m2時，第k個數(shù)一定不在nums1的后半部分棍厌，問題變?yōu)檎缶撸趎ums1的前半部分和nums2中尋找第k個數(shù)；反之不在nums2的后半部分定铜，問題也相應改變阳液，這樣搜索的范圍就減小了
代碼實現(xiàn)
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
n = len(nums1)+len(nums2)
if n%2==1:
return self.findKth(nums1, nums2, n//2)
else:
return (self.findKth(nums1, nums2, n//2)+self.findKth(nums1, nums2, n//2-1))/2
def findKth(self, nums1, nums2, k):
if not nums1:
return nums2[k]
if not nums2:
return nums1[k]
i1, i2 = len(nums1)//2, len(nums2)//2
print(i1,i2)
m1, m2 = nums1[i1], nums2[i2]
if i1 + i2 < k:
if m1 > m2:
self.findKth(nums1, nums2[i2+1], k-i2-1)
else:
self.findKth(nums1[i1+1:], nums2, k-i1-1)
else:
if m1 > m2:
self.findKth(nums1[:i1], nums2, k)
else:
self.findKth(nums1, nums2[:i2], k)
