- 4. Median of Two Sorted Arrays
- from typing import List
- class Solution:
- def findMedianSortedArrays(self, A: List[int], B: List[int]) -> float:
- m, n = len(A), len(B)
- if m> n:#A 是较短的数组
- A, B, m, n = B, A, n, m
- if n == 0:
- raise ValueError
- imin, imax, half_len = 0, m, (m + n + 1) / 2
- while imin <= imax:
- i = int((imin + imax) / 2)#i 是 A 的分割处
- j = int(half_len - i)#j 是 B 的分割处
- print(i)
- print(j)
- print('='*5)
- if i <m and B[j-1]> A[i]:
- # i is too small, must increase it
- imin = i + 1
- elif i> 0 and A[i-1]> B[j]:
- # i is too big, must decrease it
- imax = i - 1
- else:
- # i is perfect# 已经确认了边界
- if i == 0: max_of_left = B[j-1]#A 全分在了右边
- elif j == 0: max_of_left = A[i-1]#B 全分在了右边
- else: max_of_left = max(A[i-1], B[j-1])
- if (m + n) % 2 == 1:# 说明当总数是奇数时, 左边多分了一个.
- return max_of_left*1.0
- if i == m: min_of_right = B[j]
- elif j == n: min_of_right = A[i]
- else: min_of_right = min(A[i], B[j])
- return (max_of_left + min_of_right)*1.0 / 2.0
- s=Solution()
- #print(s.findMedianSortedArrays([1,2],[3,4,5,6,7,8]))# 此时 i=2,j=2. 此时 i=m
- #print(s.findMedianSortedArrays([9,10],[3,4,5]))# 此时 i=0
- #print(s.findMedianSortedArrays([1,2],[3,4]))# 此时 j=0, 只有在两者长度相等且 A 在 B 左边时, 才有 j=0
- print(s.findMedianSortedArrays([3,4],[1,2]))# 此时 j=m, 只有在两者长度相等且 A 在 B 右边时, 才有 j=m
- // 这道题确实挺难的.
来源: http://www.bubuko.com/infodetail-3096443.html