4. Median of Two Sorted Arrays
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
My Solution
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
nums1.extend(nums2)
nums1.sort()
if len(nums1) % 2 == 0:
return float((nums1[len(nums1)//2-1] + nums1[len(nums1)//2]) / 2)
else:
return float(nums1[len(nums1)//2])
Reference (转)
class Solution:
# @return a float
def findMedianSortedArrays(self, A, B):
l=len(A)+len(B)
return self.findKth(A,B,l//2) if l%2==1 else (self.findKth(A,B,l//2-1)+self.findKth(A,B,l//2))/2.0
def findKth(self,A,B,k):
if len(A)>len(B):
A,B=B,A
if not A:
return B[k]
if k==len(A)+len(B)-1:
return max(A[-1],B[-1])
i=len(A)//2
j=k-i
if A[i]>B[j]:
#Here I assume it is O(1) to get A[:i] and B[j:]. In python, it's not but in cpp it is.
return self.findKth(A[:i],B[j:],i)
else:
return self.findKth(A[i:],B[:j],j)
