問題：給定 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)快，但是容易實作的方法？