There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
Solution
- 这个问题实际上是查找底(m+n)/2和第(m+n)/2+1个元素. (第k个元素)
- 二分查找，把k分成2部分pa=
min(k/2, len(a))和pb=k-pa
- 比较A[pa]于B[pb]
** if (A[pa]<B[pb]), which means the elements from A[0] to A[pa] must exist in the first Kth elements.二分查找下一个的时候就不需要考虑A[0:pa]，他们一定在前k个元素里
** if (A[pa]>B[pb]), the same procedure is applied but we “cut” the B array.
(Median-of-Two-Sorted-Arrays.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
l1 = len(nums1)
l2 = len(nums2)
# 若总共有偶数，找到第(l1+l2)/2 和 (l1+l2)/2+1的平均数
if (l1+l2)%2 == 0:
return (self.findKth(nums1,nums2,(l1+l2)/2) + self.findKth(nums1,nums2,(l1+l2)/2+1))/2.0
else:
# 若总共有奇数，找到第(l1+l2)/2+1个就是答案
return self.findKth(nums1,nums2,(l1+l2)/2+1)
def findKth(self, nums1, nums2, k):
# 确保nums1个数比nums2少
if len(nums1) > len(nums2):
return self.findKth(nums2,nums1,k)
# 第k个就是nums[k-1]
if len(nums1) == 0:
return nums2[k-1]
# 若程序到这里，说明至少每个数组都有1个元素
if k == 1:
return min(nums1[0],nums2[0])
pa = min(k/2, len(nums1))
pb = k-pa
if nums1[pa-1] <= nums2[pb-1]:
#第k个一定在nums2中
return self.findKth(nums1[pa:], nums2, k-pa)
else:
# 第k个一定在nums1中
return self.findKth(nums1,nums2[pb:], k-pb)
if __name__ == "__main__":
sol = Solution()
sol.findMedianSortedArrays([1,2],[3,4])
|