- leetcode 4 兩個數(shù)組找中位數(shù)
給定兩個大小為 m 和 n 的有序數(shù)組 nums1 和 nums2。
請你找出這兩個有序數(shù)組的中位數(shù)，并且要求算法的時間復(fù)雜度為 O(log(m + n))。
你可以假設(shè) nums1 和 nums2 不會同時為空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
則中位數(shù)是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
則中位數(shù)是 (2 + 3)/2 = 2.5
第一道想寫的題就是leetcode4.這道題很有意思，當(dāng)然也有點難
我想先寫一個普通二分查找（不考慮一開始越界）：
def binary_search(nums, k):
l=0
r=len(nums)
while(l<r):
m=(l+r)//2
if nums[m]==k:
return m
elif nums[m]<k:
l=k+1
else:
r=k-1
可以看出，我們要寫的這道題，思路似乎差不多，也是尋找某個數(shù)，時間要求也是最多l(xiāng)og(m+n)，這妥妥查找了。
兩個數(shù)組需要轉(zhuǎn)換為一個數(shù)組的問題，但是并不能排序，那么可以這樣想：
從nums1里邊取n1個，nums2里邊取n2個，如果他們拼起來的數(shù)組是升序的，且長度剛好等于mid，那么這個mid就是我們要找的位置。然而對于兩個數(shù)組，似乎不太方便同時找兩個中點，所以不如確定nums1一共要多少個，剩下的mid-nums1[保留的]就是nums2所需要的。如果有這樣一個數(shù)組，那么標(biāo)號第[mid-1]就是我們需要的（因為數(shù)組從0開始）。
所以，對于nums1：先確定它的l和r，然后找到nums1的中點和nums2的中點，做一個比較，如果nums1[mid1]小于nums2[mid2]，那么就說明nums1左側(cè)區(qū)間太小了，要拋棄，所以l=mid1+1，否則，就太大了，所以r=mid1-1
話雖如此，但是這樣提交會錯，因為要考慮1.如果一個數(shù)組是空；2.兩個數(shù)組元素數(shù)量和是偶數(shù);3.兩個數(shù)組元素數(shù)量和是奇數(shù)。對于3，實際上不可能做到分開的兩側(cè)數(shù)量剛好，如果我們讓左側(cè)多一個數(shù)的話，也就是n1+n2=len(nums1)-n1+len(nums2)-n2+1，這樣n2=len(nums1+nums2+1)/2-n1，這樣，就算一開始是偶數(shù)個，+1操作也不會使坐標(biāo)計算錯誤。對于2.假設(shè)合成的數(shù)組為c，那么我們需要給求出c[mid-1],c[mid]的平均值，而分配下去，就是我們需要知道nums1[mid1-1], nums1[mid1], nums2[mid1-1], nums2[mid2]里邊兩個元素的平均值。
和簡單二分法不同我們的判斷條件也會變化，這是應(yīng)該是nums1[mid1]<nums2[mid2-1]，這個-1也是如此，mid-1是我們能到達的最遠，mid是不能到達的第一個，所以條件滿足的話，這一部分就會被完整拋棄，否則，右側(cè)的變化則是:r=mid1，道理一樣，因為mid是不能到達的。
最后，問題1，這個不僅僅是一開始初始化的問題，也是在運行時會碰到的問題。一個數(shù)組全被拋棄，此時mid就完全取在另一個數(shù)組。只是，如果數(shù)組長度是奇數(shù)，只需判斷和0的關(guān)系，而偶數(shù)時，需要判斷和總長度的關(guān)系。一下是代碼：
def findMedianSortedArrays(nums1, nums2):
len_n1=len(nums1)
len_n2=len(nums2)
# 這一步判斷是因為為了使nums2的長度計算時不會為負
if len_n1>len_n2:
len_n1,len_n2=len_n2,len_n1
nums1,nums2=nums2,nums1
l=0
r=len_n1
mid=(len_n1+len_n2+1)//2
# 以下是search的主體
while(l<r):
m1=(l+r)//2
m2=mid-m1
if nums1[m1]<nums2[m2-1]:
l=m1+1
else:
r=mid
# 使用l，r給mid1，mid2賦值
m1=l # 或者r，因為是一樣的
m2=mid=m1
if m1>0 and m2>0:
center1=max(nums1[m1-1],nums2[m2-1])
elif m1<=0:
center1=nums2[m2-1]
elif m2<=0: # 這里應(yīng)該寫else：，不過為了邏輯清晰就把條件全寫出來
center1=nums1[m1-1]
if (len_n1+len_n2)%2==1:
return center1
if m1<len_n1 and m2<len_n2:
center2=min(nums1[m1],nums2[m2])
elif m1>=len_n1:
center2=nums2[m2]
elif m2>=len_n2:
center2=nums1[m1]
return (center1+center2)/2.
