主題
題目連結(jié)：
題目意譯：
中位數(shù)為一個(gè)已排序整數(shù)列正中間的值。如果列表大小為偶數(shù)，則沒有正中間而此時(shí)中位數(shù)為兩個(gè)最中間的值之平均。
例如，對於 arr = [2,3,4]，中位數(shù)為 3。
例如，對於 arr = [2,3]，中位數(shù)為 (2 + 3) ÷ 2 = 2.5。
實(shí)作類別 MedianFinder：
MedianFinder() 初始化 MedianFinder 之物件。
void addNum(int num) 從資料串流把整數(shù) num 加到資料結(jié)構(gòu)中。
double findMedian() 回傳目前所有元素的中位數(shù)。答案位於與正確答案差 10^(-5) 的誤差之內(nèi)也會(huì)被接受。
限制：
-10 ^ 5 ≦ num ≦ 10 ^ 5
在呼叫 findMedian 前，資料結(jié)構(gòu)中至少會(huì)有一個(gè)元素。
最多 5 × 10 ^ 4 次呼叫將會(huì)是 addNum 和 findMedian。
進(jìn)階：
如果所有來自串流的整數(shù)數(shù)字皆介於範(fàn)圍 [0, 100] 之中，你會(huì)怎麼最佳化你的解法？
如果 99% 來自串流的整數(shù)數(shù)字皆介於範(fàn)圍 [0, 100] 之中，你會(huì)怎麼最佳化你的解法？
範(fàn)例測資：
輸入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
輸出
[null, null, null, 1.5, null, 2.0]
解釋
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 回傳 1.5 (即 (1 + 2) ÷ 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // 回傳 2.0
解題思維：
雖然可以用這題的方法，但是如同該篇下面留言所講的一樣，我們有著其他的解法。而這邊要介紹的是使用兩個(gè)堆積（Heap）或是優(yōu)先佇列（Priority Queue，通常以堆積實(shí)作）來維護(hù)得到中位數(shù)：
可以看到將當(dāng)前有的數(shù)字分成兩個(gè)部分，一個(gè)是數(shù)字較小的那一半（下稱左半）、另一個(gè)數(shù)字較大的那一半（下稱右半），而如果數(shù)量為奇數(shù)則左半會(huì)多一個(gè)。記住，右半中的任意數(shù)字應(yīng)大於等於左半中的任意數(shù)字。
觀察可得：當(dāng)目前有奇數(shù)個(gè)數(shù)字時(shí)，中位數(shù)即是左半中的最大值；當(dāng)有偶數(shù)個(gè)數(shù)字時(shí)，中位數(shù)即是左半的最大值與右半的最小值之平均。
如果我們可以一直求得每個(gè)數(shù)量下左半（右半）的最大值（最小值），則我們便可以得知每個(gè)數(shù)量下的中位數(shù)之值。而這可以使用兩個(gè)堆積來維護(hù)：對於左半我們使用最大堆積（也就是頂端節(jié)點(diǎn)為整體最大值）、對於右半則用最小堆積（也就是頂端節(jié)點(diǎn)為整體最小值）。
那實(shí)際上要怎麼維護(hù)呢？
可以看到當(dāng)一開始進(jìn)來的第一個(gè)數(shù)字應(yīng)跑到最大堆積。而接下來的數(shù)字則我們先判斷該數(shù)值是否小於左半當(dāng)前的最大值，以便判斷該數(shù)字應(yīng)進(jìn)入左半還是右半。
決定完新進(jìn)的數(shù)字要進(jìn)去哪個(gè)部分並完成插入後。接著判斷左右兩半的大小關(guān)係，而因?yàn)樯厦嫖覀冇^察出來的中位數(shù)求法。因此左半的數(shù)字個(gè)數(shù)不應(yīng)超過右半的數(shù)字個(gè)數(shù) + 1；同樣的左半的數(shù)字個(gè)數(shù)不應(yīng)低於右半的數(shù)字個(gè)數(shù)（可以看到這兩個(gè)條件如果不成立，將會(huì)無法得到正確的中位數(shù)）。
因此當(dāng)兩者大小不平衡時(shí)，我們需要把一邊的數(shù)字丟到另一邊。而我們從左半取最大丟到右半或是從右半取最小丟到左半，這兩個(gè)方式依舊保持著左半的數(shù)字都小於等於右半之特性。因此這麼做便可以平衡數(shù)字個(gè)數(shù)的差距而不必?fù)?dān)心兩邊的大小關(guān)係改變。
如上便可以利用兩個(gè)堆積使得我們隨時(shí)可以取得左半的最大值以及右半的最小值。因此每當(dāng)呼叫 findMedian() 只要根據(jù)上面的方式求得中位數(shù)即可。
進(jìn)階：
當(dāng)數(shù)字都介於 [0, 100] 這個(gè)區(qū)間時(shí)，我們可以改成求出 0（含） ～ 100（含）這 101 個(gè)數(shù)字每種數(shù)字各自現(xiàn)在有多少個(gè)。假設(shè)現(xiàn)在有 S 個(gè)數(shù)字，而我們也已經(jīng)統(tǒng)計(jì)了 101 種數(shù)字各有多少個(gè)。接著每當(dāng)遇到 findMedian() 時(shí)，我們只需要從 0 開始一路數(shù)到 100，看 floor(S ÷ 2) 位於「哪種」數(shù)字。當(dāng) S 是奇數(shù)時(shí)，該種數(shù)字就是中位數(shù)；當(dāng) S 是偶數(shù)時(shí)，還要額外判斷 S ÷ 2 + 1 又位於何種數(shù)字，兩種數(shù)字之值平均即是中位數(shù)。
那如果只有 99% 會(huì)位於 [0, 100] 這個(gè)區(qū)間內(nèi)呢？其實(shí)跟上面類似，但是會(huì)需要多兩個(gè)部分，一部分負(fù)責(zé)處理 < 0 的數(shù)字、一部分處理 > 100 的數(shù)字。然後對於每次 findMedian() 之呼叫，根據(jù) S 之值以及 [0, 100] 中的數(shù)字個(gè)數(shù)來判斷是否中位數(shù)真的位於 [0, 100] 中。如果是就按照上面的作法即可；反之，就要單獨(dú)地去範(fàn)圍外去找中位數(shù)。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
