題目連結:
題目大意:
輸入有多列(≦ 200000 列),每列給定一個整數(可以被 32 位元有號整數儲存)。對於每次輸入,請找出目前所有輸入過的數字由小排到大的中位數。
假設現在有 k 個數。如果 k 是奇數,則第 (k + 1) ÷ 2 小的數字就是中位數;如果 k 是偶數,則中位數是第 k ÷ 2 小和第 k ÷ 2 + 1 小的數字之平均。
因為我們要由小排到大(由大排到小也可以,不影響中位數的結果),而每次重新排序很浪費時間。且因為數字很多,因此每次輸入進來一個新的數字時,需要在合理時間內將其排入適當的位置。
直接掃過排好的數列再將新數字插入當然是不夠快。我們可以使用二分搜尋法(Binary Search),找到要插入的位置。但是一般的陣列仍需要線性時間把其他數字移走並讓新數字到指定位置。雖然可以用 C++ 內建的資料結構 vector 裡面的 insert 函式在時限內達成(似乎有一些特殊的最佳化方式),而我也是這麼解的。
但是,我們需要一個更好的資料結構。基本上需要一個會自動平衡的二元樹,例如紅黑樹、伸展樹等等。然後用一個指標(正常會稱為迭代器(Iterator),而不是一般的指標)保持指向我們的所求——也就是中位數所在的位置。當然對於偶數個數字,指到的位置不是真的中位數,但是可以根據迭代器找到下一個數字並與之平均。
程式語言例如 C++ 自己有平衡樹,所以可以使用該資料結構達成需求。而這方面就交給讀者們自行研究如何使用並維護上述的迭代器指向所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。