※ 引述《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)快的方法來解決這問題呢？
應該很難吧！
資料有 n^2 筆，然後時間複雜度是 O(n^2)，基本上已經是 linear time
要低於線性時間
要嘛略過一些資料
要嘛問題本身有很強的數學性質，可以直接推導答案
在這個問題當中，上面兩種策略似乎都行不太通
考慮 median-of-median algorithm 的第一回合
由於給定資料是 n 條已排序陣列，所以第一回合可以省下很多工夫，可以很快做完
但是找到中位數的中位數之後
接下來，還有可能是中位數的資料，約占全部的3/4
第二回合還是得處理 3/4 * n^2 這麼多資料，依舊是 O(n^2) 級別
即便我們已經知道 n 條已排序陣列，但是它的功效只能幫助我們略過 1/4 的資料
再加上中位數沒有什麼好的數學性質，尤其是可以用於精確計算的的數學性質
所以我覺得很難達成！

其實就是用 median of median 的演算法，只是找到median of median m 之後，用 binary search 找出每個排序的陣列中有幾個元素比 m 小，看看要找的median 比 m 大還是比 m 小。雖然每次可能只能減少 1/4 的元素，不過沒關係。每次花的時間，理論值是 O(n) 找 median of medianO(n log n) 找比 m 小的元素個數。總共應該只需要花 O(log n) 次每次都要使用排序好的陣列。

可是 problem size 不是 n^2 嗎？這樣上面的 n 都要換成 n^2

因為 n 個 size 為 n 的數列已經排序好了要算有幾個元素比 m 小時，並不是拿 n^2 個元素來比較而是去每個數列做 binary search，所以時間是 O(nlogn)

第二回合要怎麼找median of median?

每一個數列是哪個範圍的元素在候選名單中需要記下來候選範圍的資料的 median 同樣可以找 median。

其實找median of median可以用排序 不影響複雜度但是會比較容易作

應該是不得不排序 為了知道「減少1/4的元素」來自哪些陣列springman的方法看起來可行 是O(n logn logn)

但是要怎麼證明一次可以刪除O(n/4)個元素？因為到最後每一列的元素都不一樣多 原本median of median的證明法好像不能直接套用