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