FIND THE RUNNING MEDIAN - 演算法例：會跑的中位數～改變人生從解題開始～
簡單複習一下中位數以免你忘了
中位數（又稱中值，英語：Median），統計學中的專有名詞，代表一個樣本、種群或機率分布中的一個數值，其可將數值集合劃分爲相等的上下兩部分。對於有限的數集，可以通過把所有觀察值高低排序後找出正中間的一個作爲中位數。如果觀察值有偶數個，則中位數不唯一，通常取最中間的兩個數值的平均數作爲中位數。
假設今天龍哥開了一場 VIP 握手會，來參加的 VIP 共有五位，年齡由小到大分別是 12, 17, 21, 29, 38，那我們可以說 VIP 的年齡中位數是 21。 若是龍哥晚上又開了一場 VIP 床上聊天會，來參加的 VIP 共有四位，年齡由小到大分別是 20, 24, 25, 60，那我們可以說 VIP 的年齡中位數是 24.5。
怎麼用演算法解？
- 將 input 的資料排序過一遍
- 若 input 項目數量(N)是奇數，取第
ceil(N/2)項為中位數 - 若 input 項目數量(N)是偶數，取第
N/2項與N/2 + 1項相加再除以二為中位數
求中位數的演算法題都是送分題？
對於大部分有念過資訊科系的同學來說，中位數的題目都是十分簡單的，最常出現在大一學生的考卷上，考驗大學新鮮人們是否有專心在聽課堂上介紹的排序演算法。 所以…
對，中位數的演算法題都是送分題！
我一直是這樣認為的
直到我看到下面這題為止。
FIND THE RUNNING MEDIAN link
有興趣的朋友們可以點上面的那個連結去寫寫看，挑戰通過全部的 test case，成功的人就可以左轉離開了，沒成功的人請看下面詳細說明。
題目說明
- 你會收到一連串未排序過的正整數，除了第一個數字代表樣本總數量之外，其他的數字都是樣本
- 請你每收到一個樣本的時候，從所有你收到的樣本中找出一個中位數
解題說明
假設使用時間複雜度 O(nlogn) 等級的排序演算法配上原本的解題邏輯來解，最終解法時間複雜度會超過 O(n^2logn) ，這樣是過不了 hackerrank 上最後三個 test case 的。
(如果要通過 amazon 面試的第一關，必須全過)
那該怎麼辦？
大一的程式設計不夠用？只好出動大二的資料結構了！
重新思考整個題目之後，會發現我們只要設計一個二元樹結構，可讓我們直接取得中位數就行了。 典型的二元樹的插入動作時間複雜度是 O(logn)，讀取動作時間複雜度是 O(1)，所以我們最終可以獲得 O(nlogn) 的解法。
由於我們取出的時後有可能需要一次取出兩個數字，
所以我們需要兩棵樹：
- 一棵小樹專門放小於中位數的值
- 一棵大樹專門放大於中位數的值
這樣小樹可以直接使用 max heap (頭是堆中最大值的堆積)，大樹可以直接使用 min heap (頭是堆中最小值的堆積)。
同時依照中位數的定義，小樹根大樹的高度應該要一樣，所以當兩棵樹高度差超過 1 的時候，需要取出高樹的頭插入低樹裡面（聽起來怪怪的（汗))。
取出頭的動作跟插入一樣都是 O(logn)。
這樣一來，中位數就十分容易取得了：
- 當兩棵樹一樣高的時候，兩棵樹的頭相加除以 2 就是中位數。
- 當兩棵樹不一樣高的時候，高樹的頭就是中位數。
時間複雜度：
- 插入新樣本：
T(3logn + 1) - 讀取中位數：
T(2) - 整體結果：
O(nlogn)
將上面的想法實作出來之後塞進 hackerrank 裡面跑，嗯，全過，恭喜各位可以通過 amazon 面試的第一關了！
結論
以結果來說，這題的滿分關鍵是堆積，而很多人學了各種好用的樹之後，就把堆積給忘了，因此沒辦法獲得滿分、在面試上敗陣下來， 因此這題可以說是包著求中位數皮的陷阱題，在這邊分享給各位，希望對各位的人生能有所幫助。