# @link http://www.cnblogs.com/zuoyuan/p/3759682.html class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
len1 = len( nums1 )
len2 = len( nums2 )
if( len1 + len2 ) % 2 == 1:
return self.getKth(nums1,nums2,(len1+len2)/2 + 1)
else:
return ( self.getKth(nums1,nums2,(len1+len2)/2) + self.getKth(nums1,nums2,(len1+len2)/2+1) ) * 0.5 def getKth(self,nums1,nums2,k):
len1 = len(nums1)
len2 = len(nums2)
if len1 > len2:
return self.getKth(nums2,nums1,k)
if len1 == 0:
return nums2[k-1]
if k == 1:
return min( nums1[0],nums2[0])
pa = min(k/2,len1)
pb = k - pa
if nums1[pa-1] < nums2[pb-1]:
return self.getKth(nums1[pa:],nums2,pb)
else:
return self.getKth(nums1,nums2[pb:],pa)