LeetCode4 hard
题目
寻找两个正序数组的中位数
给定两个大小为m和n的正序（从小到大）数组nums1和nums2.请你找出这两个正序数组的中位数，并且要求算法时间复杂度为O(log(m+n)).
解题思路
1. 简单算法 O(m+n)
将两个数组合并成一个，利用自带的排序函数使合并后的数组有序。根据下标返回中位数。但这样时间复杂度是O(m+n),不符合题目要求。
class Solution:#64ms 33.73% O(m+n)def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:nums1.extend(nums2)nums1.sort()length=len(nums1)if length%2==0:return (nums1[length//2-1]+nums1[length//2])/2return nums1[length//2]2. 二分法 O(log(m+n))
如果对时间复杂度要求有log，通常需要用到二分查找。
寻找中位数的问题实质上是寻找第k小的数。我们比较两个数组中第k/2小的数，较小的数及他之前的数一定不会是第k小的数，这样我们每次比较可以排除一半的数，达到了O(log(m+n))的时间复杂度。当然，有一些特殊情况需要单独考虑。
class Solution:#56ms 66.72% O(log(m+n))def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:def getKthMin(k:int, nums1: List[int], nums2: List[int])->int:#特殊情况1，某一个数组为空，则直接在另一个数据找到第k小的值if not nums1:return nums2[k - 1]if not nums2:return nums1[k - 1]#特殊情况2，k==1即返回最小值if k==1:return nums1[0] if nums1[0]<=nums2[0] else nums2[0]#特殊情况3，第k//2个元素超过索引，则直接比较最后一个元素与另一个数据对应元素，此时排除的元素个数是len(较短数组），而不是k//2nums11, nums22 = nums1, nums2if k//2>len(nums2):nums11, nums22 = nums2, nums1if k//2>len(nums11):if nums11[-1]<=nums22[len(nums11)-1]:k-=len(nums11)return nums22[k - 1]else:g=k-len(nums11)return getKthMin(g, nums11, nums22[len(nums11):])#正常情况，如果nums1的元素较小，则nums1位于比较位置之前的元素一定不是第k小的元素，被排除。下一次比较从nums1的下一个位置算起。if nums1[k//2-1]<=nums2[k//2-1]:g=k-k//2return getKthMin(g,nums1[k//2:], nums2)else:g=k-k//2return getKthMin(g, nums1, nums2[k//2:])#如果总长度为偶数，中位数则为二者平均值length=len(nums1)+len(nums2)if length%2==0:return (getKthMin(length//2, nums1, nums2)+getKthMin(length//2+1, nums1, nums2))/2else:return getKthMin(length // 2 + 1, nums1, nums2)