[問題] 給定n個排好序的整數陣列 找中位數

[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)快的方法來解決這問題呢？

對於變形題，理論上是有O(n)的方法，但是比較複雜。
我也想知道有沒有比O(n^2)快，但是容易實作的方法？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 50.133.134.181
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1413240425.A.2B6.html
推 springman: 感覺上有機會比 O(n^2) 小，只是還蠻複雜的。
→ springman: 有空來想想程式要怎麼寫好了。