原題
兩個排序的數(shù)組A和B分別含有m和n個數(shù)疮装，找到兩個排序數(shù)組的中位數(shù)，要求時間復雜度應為O(log (m+n))。
樣例
給出數(shù)組A =** [1,2,3,4,5,6]** B = [2,3,4,5]，中位數(shù)3.5
給出數(shù)組A = [1,2,3] B = [4,5]，中位數(shù) 3
解題思路
- 根據(jù)題目要求的時間復雜度是O(log(m+n))可知押框，必須要有個類似于binary search一樣，每次操作可以扔一半理逊。
- 如果數(shù)組A和B一個含有n個元素橡伞，那么,
- 如果n是奇數(shù)，則中位數(shù)是合并數(shù)組的第n/2+1個數(shù)
- 如果n是偶數(shù)晋被，則中位數(shù)是合并數(shù)組的第n/2個數(shù)和n/2+1個數(shù)的平均數(shù)
- 最后為題轉(zhuǎn)化為如何求兩個排序數(shù)組的第k大的數(shù)兑徘，時間復雜度為O(log(m+n))
- 思路：每次找A的k/2的位置和B的k/2的位置的數(shù)與相比較
- 如果A[k/2] < B[k/2]，則扔掉A的前k/2個數(shù)羡洛，因為第k大的數(shù)一定不在其中挂脑。找第k大的數(shù)轉(zhuǎn)化為，在剩下的A數(shù)組和B數(shù)組中找第k/2大的數(shù)
- 如果A[k/2] >= B[k/2]欲侮，則扔掉B的前k/2個數(shù)崭闲，因為第k大的數(shù)一定不在其中。找第k大的數(shù)轉(zhuǎn)化為威蕉，在剩下的B數(shù)組和A數(shù)組中找第k/2大的數(shù)
-
注意：如果要求返回float類型刁俭，要
/ 2.0而不是/ 2
完整代碼
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.findKthNum(nums1, nums2, n / 2 + 1)
else:
return (self.findKthNum(nums1, nums2, n / 2) + self.findKthNum(nums1, nums2, n / 2 + 1)) / 2.0
def findKthNum(self, nums1, nums2, k):
if len(nums1) == 0:
return nums2[k - 1]
elif len(nums2) == 0:
return nums1[k -1]
elif k == 1:
return min(nums1[0], nums2[0])
a = nums1[k / 2 - 1] if k / 2 <= len(nums1) else None
b = nums2[k / 2 - 1] if k / 2 <= len(nums2) else None
if b is None or (a is not None and a < b):
return self.findKthNum(nums1[k / 2:], nums2, k - k / 2)
else:
return self.findKthNum(nums1, nums2[k / 2:], k - k / 2)
