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)).
You may assume nums1 and nums2 cannot be both empty.
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。
我这里把两个数组合并为一个排序后的数组，如果数组的长度是奇数，那么中间的数就是中位数，如果数组的长度是偶数，那么中位数就是位于中间的两个数的平均数。
My silly solution:
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
l = sorted(nums1 + nums2)
if len(l) % 2 == 1:
return l[len(l) // 2]
else:
return (l[len(l) // 2 - 1] + l[len(l) // 2]) / 2
alvin19940815 official solution:
class Solution:
def findMedianSortedArrays(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: float
"""
# n>=m
m, n = len(A),len(B)
if n<m:
A, B, m, n = B, A, n, m
imin, imax, halfLen = 0, m, (m+n+1)/2
while(imin <= imax):
i = int((imin+imax)/2)
j = int(halfLen)-i
if i > 0 and A[i-1] > B[j]:
imax = i - 1
elif i < m and A[i] < B[j-1]:
imin = i + 1
else:
# i is perfect
if i==0:
maxLeft = B[j-1]
elif j==0:
maxLeft = A[i-1]
else:
maxLeft = max(A[i-1], B[j-1])
if (m+n) % 2 == 1:
return maxLeft
else:
if i==m:
minRight = B[j]
elif j==n:
minRight = A[i]
else:
minRight = min(B[j],A[i])
return (maxLeft+minRight)/2
