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.作者的話
最後，您如果覺得本公眾號對您有幫助，歡迎您多多支援，轉發，謝謝！
更多刷題，請關注本公眾號演算法系列！
