: ※ 引述《FRAXIS (喔喔)》之銘言：
: : 問題：給定 n 個已排序整數陣列，每個陣列長度為 n
: : 找出 n^2 個元素中的中位數。
: : 在網路上有找到幾個討論
: : http://ppt.cc/PMvU
: : http://ppt.cc/JE1s
: : (這是變形，給定一個n by n矩陣，每行每列都排序，找中位數)
: : 但是我覺得他們的解法到最後都變成O(n^2 lg n)。
: : 而如果忽略掉每個陣列都已經排序的性質，直接在 n^2 個元素中找中位數，
: : 因為找中位數可以在線性時間內完成，
: : 所以在 n^2 個元素內找中位數只需要O(n^2)的時間，也比網頁上的解答好。
: : 有沒有比O(n^2)快的方法來解決這問題呢？
: 推 springman: 其實就是用 median of median 的演算法，只是找到 10/14 09:24
: → springman: median of median m 之後，用 binary search 找出 10/14 09:25
: → springman: 每個排序的陣列中有幾個元素比 m 小，看看要找的 10/14 09:25
: → springman: median 比 m 大還是比 m 小。 10/14 09:26
: → springman: 雖然每次可能只能減少 1/4 的元素，不過沒關係。 10/14 09:26
: → springman: 每次花的時間，理論值是 O(n) 找 median of median 10/14 09:27
: → springman: O(n log n) 找比 m 小的元素個數。 10/14 09:28
: → springman: 總共應該只需要花 O(log n) 次 10/14 09:28
: → springman: 每次都要使用排序好的陣列。 10/14 09:29
我有想到一個類似的方法，先把每列median找出來，總共有 n 個。
找出這 n 個元素的最大值 max 和最小值 min 及其所在的列max_i, min_i。
然後可以把max_i或是min_i列中刪除一半的元素 （這邊需要case分析解決base case）
這樣每回合至少會有一列的大小變成一半，所以最多有O(n lg n)個回合。
每個回合，找最大值和最小值可以依賴一個balanced binary search tree，
所以時間是O(lg n)。演算法的時間複雜度是O(n lg^2 n)。
不過這兩個方法，都只使用了每列已排序的性質。
當每行每列都已排序，有沒有比O(n lg^2 n)快的簡單方法呢？
（理論上是可以O(n) 但是蠻複雜的）