本文共 2477 字,大约阅读时间需要 8 分钟。
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)).
You may assume nums1 and nums2 cannot be both empty.
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
注意到这道题要求的时间复杂度是O(log(m+n)),如果说是O(n),那很简单一次遍历排个序就有了,主要难的就是log(m+n)的时间复杂度。看到log,这题肯定是要用二分法的,说实话想了挺久还是没想出来,后面借鉴了别人的思路
原思路是用英文写的(建议先去看下英文概述的图,再来看我讲的规律会好点),我简单概述一下核心和注意的点,后面会放别人想法的链接
我们直接想,假设我们的中位数是在A[i],会有什么样的规律可循。
可以知道中位数左边的数都小于它,右边的数都大于它,并且各占一半(假设数组长度和是偶数)
这就意味着A数组从A[0]到A[i-1],B数组从B[0]到B[j-1]都要小于A[i]
i和j有什么关系,我们知道中位数两边个数相等
这说明 i+j=(m+n)/2
j就可以用i来表示
其实就相当于我们现在要找的是从数组A的某个位置切一刀,这一刀把AB两个数组分成了两个模块
我们用二分搜索来找这一刀的位置
假设切的位置A是在i,B是在j
i=(imin+imax)/2
只要满足A[i]>A[j-1] and A[i-1]<A[j],那么这就到了正确的划分,这样我们只需要比较
A[i]和A[j]里选小的那个,A[i-1],A[j-1]里选大的那个(假设数组长度和是偶数,奇数的话也很容易)
这两个数就是中位数,
如果不满足A[i]>A[j-1],说明A[i]小了,让i增大就行了,这时候更新左边界
imin=i+1,搜索右边那一半
如果不满足A[i-1]<A[j],说明A[i-1]太大了,更新右边界
imax=i-1
这就是主要的思路,其实这道题主要的难点是,如何处理边界
i=0,=lenA,j=0,=lenA
的时候,怎么处理找那两个中位数
然后提供一个如果数组长度是奇数的时候的处理方法:
我是让j=(lenA+lenB)/2
因为/会取整丢弃小数位,这样子使得当数组长度和为奇数的时候,左部分会少一位(数组B的0~j是左部分),这样就可以保证如果数组长度和数奇数的话,中位数就是右边部分的最小值
同时数组B长度一定得大于数组A,不然j可能会是负数
这道题主要难点就是二分的方法和边界的处理,特别是左部分最大值和右部分的最小值在边界的时候应该怎么找
更多leetcode算法题解法请关注我的专栏或关注我
欢迎大家一起套路一起刷题一起ac
class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: lenA=len(nums1) lenB=len(nums2) if lenA>lenB: nums1,nums2,lenA,lenB=nums2,nums1,lenB,lenA imin,imax=0,lenA, mid=int((lenA+lenB)/2) while imin<=imax: i=int((imin+imax)/2) j=mid-i if inums2[j]: imax=i-1 else: if lenA == 0: if (lenA + lenB) % 2 == 0: return (nums2[int(lenB / 2)] + nums2[int(lenB / 2) - 1]) / 2 else: return nums2[int(lenB / 2)] min_right,max_left=0,0 if i==0:max_left=nums2[j-1] elif j==0:max_left=nums1[i-1] else: max_left=max(nums1[i-1],nums2[j-1]) if i==lenA:min_right=nums2[j] elif j==lenB:min_right=nums1[i] else:min_right=min(nums1[i],nums2[j]) if (lenA+lenB)%2==0: return (max_left+min_right)/2 else: return min_right
转载地址:http://lqmrb.baihongyu.com/