題目
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
python
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
if len(nums1) >= len(nums2):
tem1 = nums1
tem2 = nums2
else:
tem1 = nums2
tem2 = nums1
begin1 = 0
end1 = len(tem1) - 1
begin2 = 0
end2 = len(tem2) - 1
m = (end1 + end2 + 2) // 2
l_length = 0
n1=len(tem1)
n2=len(tem2)
while begin1 < end1 and begin2 < end2:
middle = (begin2 + end2) // 2
index = Solution.binary_search(tem1[begin1:end1 + 1], tem2[middle])
l_length = (middle + 1 + index+begin1)
if l_length > m:
end1 = begin1 + index - 1
end2 = middle
elif l_length < m:
begin1 += index
begin2 = middle + 1
else:
x= tem1[begin1+index] if tem1[begin1+index]<tem2[middle+1] else tem2[middle+1]
if (len(tem1) + len(tem2)) % 2 != 0:
return x
else:
return (x + tem2[middle]) / 2.0
position=m-begin1-begin2
if end1-begin1>=0 and end2-begin2>=0:
if end2-begin2 > end1-begin1:
tem3 = tem2[begin2:end2 + 1]
target = tem1[begin1]
else:
tem3 = tem1[begin1:end1 + 1]
target = tem2[begin2]
index = Solution.binary_search(tem3, target)
l_length += index
tem3.insert(index,target)
else:
tem3= tem2 if len(tem2)>len(tem1) else tem1
if (n1+ n2) % 2 != 0:
return tem3[position]
else:
x=tem3[position]+tem3[position-1]
return x / 2.0
@staticmethod
def binary_search(num1, target):
start = 0
end = len(num1) - 1
middle = (start + end) // 2
while start < end:
if num1[middle] > target:
end = middle - 1
elif num1[middle] < target:
start = middle + 1
else:
return middle
middle = (end + start) // 2
if end < 0:
return 0
return end if num1[end] >= target else end + 1
