4.寻找两个有序数组的中位数(hard)
2019-05-12 本文已影响0人
genggejianyi
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
- show the code:
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
l = len(nums1) + len(nums2)
return self.findkth(nums1,nums2,l//2) if l%2==1 else (self.findkth(nums1,nums2,l//2-1)+self.findkth(nums1,nums2,l//2))/2.
def findkth(self,a,b,k):
if not a:
return b[k]
if not b:
return a[k]
ia,ib = len(a)//2,len(b)//2
na,nb = a[ia],b[ib]
#如果a b长度都为奇数，则会出现ia+ib<k
if ia+ib < k:
if na > nb:
return self.findkth(a,b[ib+1:],k-ib-1)
else:
return self.findkth(a[ia+1:],b,k-ia-1)
else:
if na > nb:
return self.findkth(a[:ia],b,k)
else:
return self.findkth(a,b[:ib],k)
- 算法的关键是要实现一个函数
findkth，他可以从两个排序数组中取出第k个数， - 这里由于每次都是对长为m和n的数组取半，所以时间复杂度为
O(log(m+n)) - 一直没太看懂关于代码中的if判断部分的逻辑，leetcode上这个人解释的还可以：
if ia + ib < k: means the k-th element still exist in some larger part of the array
if na < nb => la < na < nb: solution can't exist in la
if na > nb => lb < nb < na: solution can't exist in lb
since we are deleted some smaller part, original we are seeking for the k-th, now we are seeking for the k - (len(smaller part)) th in the remaining two array
if ia + ib > k: means the k-th element still exist in some smaller part of the array
if na < nb => na < nb < rb: solution can't exist in rb
if na > nb => nb < na < ra: solution can't exist in ra
since we are deleted some larger part, we are still finding the k-th element in the array
- 其实
ia + ib < k的情况就是k比较大，说明第k个数肯定在两个数组后半部分，相反，k比较小的情况就是在前半部分。 - 在判断了k应该在left部分还是right部分后，进一步比较两个数组中位数的大小，来决定是否抛弃某一部分：抛弃有四种情况—
aleft,bleft,aright,bright。
