题目链接在这里:
是一道很好的二分题,一开始没有想到越界怎么处理,忽略了(m+n)/2一定介于min(n,m)和max(n,m)之间,因此如果确定在短的数组上进行二分就不用考虑越界问题了,其次没有考虑到当划分之后,左边区间的每一个点都小于右边区间的点,这是一个很重要的性质,但是最开始在当前策略有效性的判断上并没有考虑到这个,而是单独的对每一个数组的边界分别进行判断。
1 class Solution(object): 2 def findMedianSortedArrays(self, nums1, nums2) -> float: 3 n1 = len(nums1) 4 n2 = len(nums2) 5 m = (n1 + n2+1) // 2 6 if n1 > n2: 7 return Solution.findMedianSortedArrays(self, nums2, nums1) 8 low, high = 0, n1 9 while low <= high: 10 mid = (low + high) // 2 11 midd = m - mid 12 13 # print("low:",low,"high:",high,"mid:",mid) 14 lw1 = -1e7 if mid == 0 else nums1[mid-1] 15 lw2 = -1e7 if midd == 0 else nums2[midd-1] 16 hgh = 1e7 if mid == n1 else nums1[mid] 17 hgh2 = 1e7 if midd == n2 else nums2[midd] 18 19 if lw1<=hgh2: 20 low = mid+1 21 an1,an2 = max(lw1,lw2),min(hgh,hgh2) 22 # print (lw1, lw2) 23 else: 24 high = mid - 1 25 if ((n1+n2)%2==1): 26 return an1 27 else: 28 return (an1+an2)/2.0 29 30 31 if __name__ == "__main__": 32 nums1 = [1, 2] 33 nums2 = [3, 4] 34 ans = Solution.findMedianSortedArrays(self=0, nums1=nums1, nums2=nums2) 35 print(ans)
标签:二分,正序,中位数,nums1,数组,n1,n2,Leetcode,nums2 From: https://www.cnblogs.com/keximeiruguo/p/17236817.html