- leetcode 4 兩個(gè)數(shù)組找中位數(shù)
給定兩個(gè)大小為 m 和 n 的有序數(shù)組 nums1 和 nums2。
請(qǐng)你找出這兩個(gè)有序數(shù)組的中位數(shù)嘿般，并且要求算法的時(shí)間復(fù)雜度為 O(log(m + n))。
你可以假設(shè) nums1 和 nums2 不會(huì)同時(shí)為空。
示例 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)然也有點(diǎn)難
我想先寫一個(gè)普通二分查找（不考慮一開始越界）：
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
可以看出至壤，我們要寫的這道題，思路似乎差不多枢纠，也是尋找某個(gè)數(shù)像街，時(shí)間要求也是最多l(xiāng)og(m+n)，這妥妥查找了。
兩個(gè)數(shù)組需要轉(zhuǎn)換為一個(gè)數(shù)組的問題镰绎，但是并不能排序脓斩，那么可以這樣想：
從nums1里邊取n1個(gè)，nums2里邊取n2個(gè)跟狱，如果他們拼起來的數(shù)組是升序的俭厚，且長(zhǎng)度剛好等于mid，那么這個(gè)mid就是我們要找的位置驶臊。然而對(duì)于兩個(gè)數(shù)組挪挤，似乎不太方便同時(shí)找兩個(gè)中點(diǎn)，所以不如確定nums1一共要多少個(gè)关翎，剩下的mid-nums1[保留的]就是nums2所需要的扛门。如果有這樣一個(gè)數(shù)組，那么標(biāo)號(hào)第[mid-1]就是我們需要的（因?yàn)閿?shù)組從0開始）纵寝。
所以论寨，對(duì)于nums1：先確定它的l和r，然后找到nums1的中點(diǎn)和nums2的中點(diǎn)爽茴，做一個(gè)比較葬凳，如果nums1[mid1]小于nums2[mid2]，那么就說明nums1左側(cè)區(qū)間太小了室奏，要拋棄火焰，所以l=mid1+1，否則胧沫，就太大了昌简，所以r=mid1-1
話雖如此，但是這樣提交會(huì)錯(cuò)绒怨，因?yàn)橐紤]1.如果一個(gè)數(shù)組是空纯赎；2.兩個(gè)數(shù)組元素?cái)?shù)量和是偶數(shù);3.兩個(gè)數(shù)組元素?cái)?shù)量和是奇數(shù)。對(duì)于3南蹂，實(shí)際上不可能做到分開的兩側(cè)數(shù)量剛好犬金，如果我們讓左側(cè)多一個(gè)數(shù)的話，也就是n1+n2=len(nums1)-n1+len(nums2)-n2+1六剥，這樣n2=len(nums1+nums2+1)/2-n1晚顷，這樣，就算一開始是偶數(shù)個(gè)仗考，+1操作也不會(huì)使坐標(biāo)計(jì)算錯(cuò)誤。對(duì)于2.假設(shè)合成的數(shù)組為c词爬，那么我們需要給求出c[mid-1],c[mid]的平均值秃嗜，而分配下去，就是我們需要知道nums1[mid1-1], nums1[mid1], nums2[mid1-1], nums2[mid2]里邊兩個(gè)元素的平均值。
和簡(jiǎn)單二分法不同我們的判斷條件也會(huì)變化锅锨，這是應(yīng)該是nums1[mid1]<nums2[mid2-1]叽赊，這個(gè)-1也是如此，mid-1是我們能到達(dá)的最遠(yuǎn)寥裂，mid是不能到達(dá)的第一個(gè)蛀缝，所以條件滿足的話冯乘，這一部分就會(huì)被完整拋棄，否則塔橡，右側(cè)的變化則是:r=mid1，道理一樣霜第，因?yàn)閙id是不能到達(dá)的葛家。
最后，問題1泌类，這個(gè)不僅僅是一開始初始化的問題癞谒，也是在運(yùn)行時(shí)會(huì)碰到的問題。一個(gè)數(shù)組全被拋棄刃榨，此時(shí)mid就完全取在另一個(gè)數(shù)組弹砚。只是，如果數(shù)組長(zhǎng)度是奇數(shù)枢希，只需判斷和0的關(guān)系桌吃，而偶數(shù)時(shí)，需要判斷和總長(zhǎng)度的關(guān)系晴玖。一下是代碼：
def findMedianSortedArrays(nums1, nums2):
len_n1=len(nums1)
len_n2=len(nums2)
# 這一步判斷是因?yàn)闉榱耸筺ums2的長(zhǎng)度計(jì)算時(shí)不會(huì)為負(fù)
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呕屎，因?yàn)槭且粯拥? 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.
