LeetCode攀登之旅(4)
- 2019 年 10 月 5 日
- 笔记
LeetCode攀登之旅(4)
0.说在前面
1.两个排序数组中位数
2.二分查找法
3.作者的话
0.说在前面
本节主要研究如何用二分查找算法去实现两个排序数组中位数，以及如何用python去实现。
1.两个排序数组中位数
原题如下：
给定两个大小为 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
对于这道题而言，采用下面这个方法是最容易想到的，直接将两个有序的数组或者说列表进行合并，而在python中合并直接是相加就可以了。拼接后，只需要排序，便可以得到一个有序的list，那么对这个list进行操作取其中的中位数即可。这个方法虽然快捷，也可以在leetcode上通过，但是其时间复杂度不满足题意。
下面这段代码的空间复杂度为O(m+n)，时间复杂度为O(1)(这里的m，n分别为nums1与mums2的长度，对于时间复杂度，这里的len(t)的时间复杂度为O(1)，而对于其他的操作只是单运算，没有涉及循环，故最后的时间复杂度为O(1)。而空间复杂度则按照t的长度(m+n))计算。
因为O(1)<O(log(m+n))，故可以通过。
class Solution: def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ t = nums1+nums2 # 两个拼接 t.sort(); # 合并后排序 l = len(t) medium = l//2 # 只取整数部分 if l%2==1: return float(t[medium]) # 奇数直接返回中间 else: return (t[medium-1]+t[medium])/2.0 # 偶数返回前后相加除以2
2.二分查找法
二分查找法，称折半查找或者对数搜索。
在考研时，考数据结构，记得用此方法的时间复杂度为log(n)。
假设总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k，其中k就是循环的次数。 由于n/2^k取整后>=1，即令n/2^k=1， 可得k=log2n,（是以2为底，n的对数）
对于上述这道题而言，采用这个二分查找法，可以很精确的得到相对应的时间复杂度，满足题意。
下面来阐述二分查找法在本题中的思想。
对于求中位数，分为两种情况，分别为偶数与奇数情况。
（1）当两个数组的长度之和为偶数时，最终得到的中位数为两个中间数之和除以2；
（2）而当两个数组的长度之和为奇数时，最终得到的中位数刚好为中间数。
题中所知，两个数组为有序数组，那么我们能否按照下手稿所示，通过切分，将nums1切分为左右两部分，nums2同此操作，最后有四个数，分别是x2,x3,y5,y6为我们最终中位数的考量范围。
如果此时恰好x2<y6，并且y5<x3那么我们此时得到了最终的左右区间。
此时如果两个数组之和为奇数，那么直接获取在x2与y5中取最大值，即为最终结果。
如果为偶数，则需要计算左边x2与y5的最大值，x3与y6的最小值，最大值与最小值之和除以2即为我们的结果。
如果当x2与y6 或者 y5与x3两组比较过程中发现，至少有一组不满足以上条件，那么继续寻找划分，至于具体怎么划分，看后面的例子(参考以下手稿)即可。
二分查找模型图
例子推导图1
例子推导图2
【python实现】
实现逻辑如下：
（1）首先比较两个数组的长度，将nums1存储长度较小的，nums2存储长度较大的，便于后面的划分;
（2）定义循环的区间low与hight;
（3）首次的X左区间取上述循环区间范围(这里看手稿)；
（4）partitionY-1就是上述的y5，partitionX为上述的x3，此时就得让x的左区间扩大，那么也就是让low往上升，便可以达到增大的效果，然后逐步逼近；
（5）partitionX-1就是上述的x2，partitionY就是上述的y6,当x2>y6时，此时左边数字太大，得右移，即让X的左区间缩小，也就是让high减小，然后逐步逼近；
（6）前面讨论时没有讨论到边界问题的，所以其他的情况则是讨论边界特殊化；
（7）当nums1左区间直接为0，也就是如nums1=[5,6],nums2=[3,4]这种情况，那么此时左边最大是参考的左区间y或者nums2，同理nums2左区间直接为0，则参考左区间x或者nums1；
（8）此时对于左区间直接可求出来，那么只要两个数组的总和为奇数，直接取下面最大
nums1[partitionX-1],nums2[partitionY-1]
或者上述的(7)的两种情况。
（9）最后就是右区间处理，同左区间，求出右区间最小，然后与上述的左区间最大值求和除以2即为偶数情况下的中位数。
class Solution: def findMedianSortedArrays(self, nums1, nums2): if len(nums1) > len(nums2): return self.findMedianSortedArrays(nums2,nums1) x = len(nums1) y = len(nums2) low = 0 high = x while low <= high: partitionX = int((low+high)/2) partitionY = int((x+y+1)/2 - partitionX) if partitionX<x and nums2[partitionY-1]>nums1[partitionX]: low = partitionX + 1 elif partitionX>0 and nums1[partitionX-1]>nums2[partitionY]: high = partitionX - 1 else: if partitionX==0: maxLeft = nums2[partitionY-1] elif partitionY==0: maxLeft = nums1[partitionX-1] else: maxLeft = max(nums1[partitionX-1],nums2[partitionY-1]) if (x+y)%2==1: return maxLeft if partitionX == x: minRight = nums2[partitionY] elif partitionY == y: minRight = nums1[partitionX] else: minRight = min(nums1[partitionX],nums2[partitionY]) return (maxLeft+minRight)/2.0 nums1 = [1,10,12] nums2 = [3] s = Solution() res = s.findMedianSortedArrays(nums1,nums2) print(res)
最后看一下提交的耗及击败人数，95%左右，这个是最好的结果，有时候是60%左右，所以不能完全看这个。
提交结果图
3.作者的话
最后，您如果觉得本公众号对您有帮助，欢迎您多多支持，转发，谢谢！
更多刷题，请关注本公众号算法系列！
