[問題] 給定n個排好序的整數陣列 找中位數
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間10年前 (2014/10/14 06:47)推噓1(1推 0噓 1→)留言2則, 1人參與討論串1/8 (看更多)
問題：給定 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
推
10/14 08:54, , 1F
10/14 08:54, 1F
→
10/14 08:56, , 2F
10/14 08:56, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 8 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
