兩個(gè)排序數(shù)組的中位數(shù)

給定兩個(gè)大小為 m 和 n 的有序數(shù)組nums1?和nums2?。

請(qǐng)找出這兩個(gè)有序數(shù)組的中位數(shù)。要求算法的時(shí)間復(fù)雜度為?O(log (m+n)) 。

示例 1:

nums1 = [1, 3]

nums2 = [2]

中位數(shù)是 2.0

示例 2:

nums1 = [1, 2]

nums2 = [3, 4]

中位數(shù)是 (2 + 3)/2 = 2.5

class Solution:

? ? def findMedianSortedArrays(self, nums1, nums2):

? ? ? ? """

? ? ? ? :type nums1: List[int]

? ? ? ? :type nums2: List[int]

? ? ? ? :rtype: float

? ? ? ? """

? ? ? ? nums1_len = len(nums1)

? ? ? ? nums2_len = len(nums2)

? ? ? ? if nums1_len==0:

? ? ? ? ? ? if nums2_len==0:

? ? ? ? ? ? ? ? return

? ? ? ? ? ? else:

? ? ? ? ? ? ? ? return (nums2[~nums2_len//2]+nums2[nums2_len//2])/2

? ? ? ? if nums2_len==0:

? ? ? ? ? ? if nums1_len==0:

? ? ? ? ? ? ? ? return

? ? ? ? ? ? else:

? ? ? ? ? ? ? ? return (nums1[~nums1_len//2]+nums1[nums1_len//2])/2

? ? ? ? su = 0

? ? ? ? result=[]

? ? ? ? while len(nums1) and len(nums2):

????????????if nums1[0]<nums2[0]:

????????????????result.append(nums1.pop(0))

????????????else:

????????????????result.append(nums2.pop(0))

????????if len(nums1):

????????????result+=nums1

????????elif len(nums2):

????????????result+=nums2

????????return (result[(nums1_len+nums2_len)//2]+result[~(nums1_len+nums2_len)//2])/2