难度:hard

Description:

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)).

有两个已排好序的数组各自长度为m 和n，找到这两个数组的中位数，总体时间复杂度应当是O(log(m + n))

Example:

nums1 = [1, 3]nums2 = [2]The median is 2.0Example 2:nums1 = [1, 2]nums2 = [3, 4]The median is (2 + 3)/2 = 2.5

Solution:

 

@

 

class Solution:#         """#         :type nums1: List[int]#         :type nums2: List[int]#         :rtype: float#         """    def findMedianSortedArrays(self, A, B):        def kthSmall(A, B, i1, i2, k):            lenA, lenB = len(A), len(B)            if i1 >= lenA: return B[k - 1]            if i2 >= lenB: return A[k - 1]            if k == 1: return min(A[i1], B[i2])            if lenA - i1 > lenB - i2: return kthSmall(B, A, i2, i1, k)            pa = min(lenA - i1, k / 2)            pb = k - pa            return kthSmall(A, B, i1 + pa, i2, pb) if A[i1 + pa - 1] < B[i2 + pb - 1] else kthSmall(A, B, i1, i2 + pb, pa)        lenAB = len(A) + len(B)        return kthSmall(A, B, 0, 0, lenAB / 2 + 1) if lenAB % 2 else 0.5 * (kthSmall(A, B, 0, 0, lenAB / 2)\                                                                            + kthSmall(A, B, 0, 0, lenAB / 2 + 1))

　　

// 取整除 - 返回商的整数部分