Median of Two Sorted Arrays
這是一個(gè)leetcode上的算法題目，標(biāo)記為hard。具體描述如下：
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
leetcode上要求實(shí)現(xiàn)接口如下：
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
在做題之前，首先要明白什么是中位數(shù)。以下是來自某度的解釋：
中位數(shù)（又稱中值，英語：Median），統(tǒng)計(jì)學(xué)中的專有名詞，代表一個(gè)樣本、種群或概率分布中的一個(gè)數(shù)值，其可將數(shù)值集合劃分為相等的上下兩部分。對(duì)于有限的數(shù)集，可以通過把所有觀察值高低排序后找出正中間的一個(gè)作為中位數(shù)。如果觀察值有偶數(shù)個(gè)，通常取最中間的兩個(gè)數(shù)值的平均數(shù)作為中位數(shù)。
舉個(gè)栗子，數(shù)列[1,2,2,3,3,4]的中位數(shù)為2.5。兩個(gè)序列的中位數(shù)則是將兩個(gè)數(shù)組merge到同一個(gè)序列中，然后取中位數(shù)。栗子又來了[1,3,7,8]和[2,4,5,6]的中位數(shù)是4.5。
看到算法中提到的時(shí)間復(fù)雜度為log(m+n)，很明顯，這里需要二分搜索。
二分搜索的挑戰(zhàn)
Knuth在其鴻篇巨制The Art of Computer Programming, volume3，Sorting and Searching的6.2.1節(jié)曾指出，雖然第一篇二分搜索論文在1946年就發(fā)表了，但第一個(gè)沒有錯(cuò)誤的二分搜索程序卻直到1962年才出現(xiàn)。所以，的確很難。繼續(xù)閱讀下文之前，各位讀者不妨先拿出紙筆，花幾分鐘粗略設(shè)計(jì)一下這個(gè)題目的算法。
設(shè)計(jì)實(shí)現(xiàn)
回到題目，設(shè)兩個(gè)有序數(shù)組為A和B，長(zhǎng)度分別為m、n，如何才能最快的找到中位數(shù)呢。不失一般性，可以假定m 小于等于 n,原因是A和B的中位數(shù)必然等于B和A的中位數(shù)，原因是AB的順序并不影響AB組合后的序列，因此得證。
確定邊界
二分查找，每一步都需要縮小搜索的范圍，那么不難想到，本題一個(gè)可以縮小搜索范圍的做法是通過比較兩個(gè)數(shù)組各自的中位數(shù)m1,m2，有以下三種情況來區(qū)分（數(shù)組中冒號(hào)是借用python切片表達(dá)）：
- m1 == m2, 中大獎(jiǎng)，直接返回m1(或m2）
- m1 < m2, 返回?cái)?shù)組A[?:?]和B[?:?] 的中位數(shù)
- m1 > m2, 返回?cái)?shù)組A[?:?] 和 B[?:?]的中位數(shù)
上述列表中的邊界中有諸多問號(hào)，這也是二分查找的關(guān)鍵之一。我們通過分析分別填上，考慮下面兩個(gè)因素：
- 中位數(shù)在序列包含元素的奇偶性上表現(xiàn)不同：如果序列元素個(gè)數(shù)為奇數(shù)作為中位數(shù)是數(shù)組中的某數(shù)，否則是兩個(gè)數(shù)的平均值。所以在處理邊界上，也是和奇偶相關(guān)的。
- 范圍縮小的一致性：這里指的并不是等比例，而是具體的數(shù)字。即當(dāng)數(shù)組A減少了n個(gè)元素時(shí)，數(shù)組B也必須減少n個(gè)，否則結(jié)果肯定是不對(duì)的，試想A=[2,2], B=[1,2,3...8,9]。
基于這兩點(diǎn)，
if nums1 and nums2:
m1 = findMedianOfSingleSortedArray(nums1)
m2 = findMedianOfSingleSortedArray(nums2)
if m1 == m2:
return m1
if m1 < m2:
if len1 % 2 == 0:
return self.findMedianSortedArrays(nums1[len1 / 2 - 1:], nums2[:len2 - len1 / 2 + 1])
return self.findMedianSortedArrays(nums1[len1 / 2:], nums2[: len2 - len1 / 2])
else:
if len1 % 2 == 0:
return self.findMedianSortedArrays(nums1[:len1 / 2 + 1 ], nums2[len1 / 2 - 1:])
return self.findMedianSortedArrays(nums1[:len1 / 2 + 1 ], nums2[len1 / 2:])
邊界確定后，下一步就是要找到結(jié)束條件了。
結(jié)束條件
開始之前，還是慣例，希望讀者能先思考一下。何時(shí)終止二分查找。
同時(shí)，這里先插播一個(gè)有意思的感覺：做英語選擇題拿不太準(zhǔn)時(shí)，比如第一感覺選A，然后修改了C，結(jié)果改錯(cuò)了。然后英語老師強(qiáng)調(diào)第一感覺很重要 (其實(shí)頗有點(diǎn)孕婦效應(yīng)的感覺)。 數(shù)學(xué)的題目第一感覺選B，后來仔細(xì)推理，原來D才是正確答案，數(shù)學(xué)老師強(qiáng)調(diào)的是千萬別信第一感覺。當(dāng)然不排除邪惡的數(shù)學(xué)出題人故意挖坑給大家?；氐竭@個(gè)題目，其實(shí)的確也是個(gè)數(shù)學(xué)題，小坑呢，也是有的：
當(dāng)范圍逐漸縮小，是否最終是其中一個(gè)數(shù)組變?yōu)榭眨缓笥?jì)算另外一個(gè)數(shù)組的中位數(shù)就可以了呢？估計(jì)我不說你也能猜出來，這個(gè)想法是錯(cuò)的。原因就在于，有可能中位數(shù)包含在了逐漸縮小的范圍中，尤其是在最后變?yōu)榭盏闹耙欢螘r(shí)間。
如果不為空，那各個(gè)數(shù)組包含多少元素時(shí)應(yīng)該結(jié)束呢。仔細(xì)一想，這取決與最后的中位數(shù)到底需要幾個(gè)數(shù)字才能算出來，答案是，當(dāng)序列總數(shù)是偶數(shù)時(shí)，需要2個(gè)，奇數(shù)時(shí)，需要1個(gè)。嘗試解釋一下原因：
假設(shè)[2,3]和[0,1,5,6]這種情況，[2,3]是不可再縮減的，因?yàn)橐坏┰倏s小范圍，那么中位數(shù)就無法得出了。同理，可得出奇數(shù)時(shí)需要1個(gè)的結(jié)論。
那么結(jié)束條件，也不難得出,
if len1 == 1:
if len2 % 2 == 0:
return least_1_even(nums1, nums2)
else:
return least_1_odd(nums1, nums2)
if len1 == 2:
if len2 % 2 == 0:
return least_2_even(nums1, nums2)
else:
return least_2_odd(nums1, nums2)
簡(jiǎn)單解釋一下，為何只需要判斷第一個(gè)數(shù)組長(zhǎng)度是否到達(dá)了1和2。因?yàn)橹凹俣ˋ的長(zhǎng)度小于B，并且我們?cè)诳s小范圍時(shí)，總是縮小相同的數(shù)目。所以必然是A先達(dá)到1、2。不需要關(guān)注B的長(zhǎng)度。一個(gè)數(shù)組長(zhǎng)度為1或2，另外一個(gè)數(shù)組長(zhǎng)度為奇數(shù)或偶數(shù)需要不同處理，這里都是苦力活，即比較A中的1個(gè)或2個(gè)數(shù)字與B的中位數(shù)的大小關(guān)系。具體的參考代碼，邏輯比較簡(jiǎn)單，但需要非常仔細(xì)。千萬不要遺漏任何一種情況。
def least_2_even(nums1, nums2):
a, b = nums1[0],nums1[1]
len2 = len(nums2)
p, q = nums2[len2 / 2 - 1], nums2[len2 / 2]
if b <= q and p <= a:
return (a + b) / 2.
if b <= p:
if len2 > 2:
return (max(b, nums2[len2 / 2 - 2]) + p) / 2.
return (b + p) / 2.
if a >= q:
if len2 > 2:
return (min(a, nums2[len2 / 2 + 1]) + q) / 2.
return (a + q) / 2.
if a <=p and q <=b:
return (p + q) / 2.
if p <= a <= q <= b:
return (a + q) / 2.
return (b + p) / 2.
def least_2_odd(nums1, nums2):
a, b = nums1[0],nums1[1]
len2 = len(nums2)
m = nums2[len2 / 2]
if a <= m <= b:
return m
if b <= m:
if len2 > 1:
return max(b, nums2[len2 / 2 - 1])
return b
if m <= a:
if len2 > 1:
return min(a, nums2[len2 / 2 + 1])
return a
def least_1_odd(nums1, nums2):
a = nums1[0]
len2 = len(nums2)
m = nums2[len2 / 2]
if len2 > 1:
if a >= nums2[len2 / 2]:
return (min(a, nums2[len2 / 2 + 1]) + m) / 2.
else:
return (max(a, nums2[len2 / 2 - 1]) + m) / 2.
else:
return (a + m) / 2.
def least_1_even(nums1, nums2):
a = nums1[0]
len2 = len(nums2)
p, q = nums2[len2 / 2 - 1], nums2[len2 / 2]
if p <= a <= q:
return a
if a < p:
return p
return q
例外
先別急著提交代碼，還有一種異常情況需要處理呢。
- A or B 為空：直接返回不空的數(shù)組的中位數(shù)
- A and B都為空，題目不存在這種情況，忽略
代碼：
if not nums1:
return findMedianOfSingleSortedArray(nums2)
if not nums2:
return findMedianOfSingleSortedArray(nums1)
附上工具函數(shù)：
def findMedianOfSingleSortedArray(l):
''' Array l must not be []'''
length = len(l)
if length % 2 == 0:
return (l[length/2] + l[length /2 - 1])/2.
return l[length/2]
OK，完成。
時(shí)間復(fù)雜度分析
對(duì)于數(shù)組A來講，算法在每一步都能夠縮短搜索范圍一半，直至元素個(gè)數(shù)為2。這需要log(m)次操作，當(dāng)兩個(gè)數(shù)組元素分別個(gè)數(shù)為2和n-m+2時(shí)，需要常數(shù)次比較即可獲得中位數(shù)，因此該算法時(shí)間復(fù)雜度為O(log(min(m,n))),是快于題目給出的O(log(m+n))的。（對(duì)于python的切片操作，可以有等價(jià)的傳遞數(shù)組index的O(1)的方式替代，故此處省略不記。）
總結(jié)
正如前面提到的，二分搜索的代碼其實(shí)坑很多，整數(shù)除2到底是取上限還是下限，類似off-by-one則是每次寫都會(huì)碰到。但我們只要時(shí)刻銘記二分搜索中的三個(gè)部分，就能夠強(qiáng)迫自己保持清醒了：
- 初始化: 循環(huán)不變式(loop invariant)始終為真
- 保持: 如果在某次迭代開始時(shí)以及循環(huán)執(zhí)行時(shí)，不變式都為真，那么循環(huán)執(zhí)行完畢不變式依然為真
- 終止： 循環(huán)能夠終止，并且得到期望結(jié)果。
所有代碼在我的github上
