Re: [問題] 給定n個排好序的整數陣列 找中位數
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間10年前 (2014/10/14 20:08)推噓9(9推 0噓 17→)留言26則, 3人參與討論串3/8 (看更多)
: ※ 引述《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) 但是蠻複雜的）
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.148
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1413288532.A.2C4.html
推
10/14 22:56, , 1F
10/14 22:56, 1F
→
10/14 22:56, , 2F
10/14 22:56, 2F
→
10/14 23:57, , 3F
10/14 23:57, 3F
推
10/15 01:11, , 4F
10/15 01:11, 4F
→
10/15 01:31, , 5F
10/15 01:31, 5F
推
10/15 01:52, , 6F
10/15 01:52, 6F
→
10/15 01:53, , 7F
10/15 01:53, 7F
→
10/15 01:54, , 8F
10/15 01:54, 8F
→
10/15 02:27, , 9F
10/15 02:27, 9F
推
10/15 02:37, , 10F
10/15 02:37, 10F
→
10/15 02:46, , 11F
10/15 02:46, 11F
推
10/15 02:50, , 12F
10/15 02:50, 12F
→
10/15 02:53, , 13F
10/15 02:53, 13F
推
10/15 02:53, , 14F
10/15 02:53, 14F
→
10/15 02:53, , 15F
10/15 02:53, 15F
→
10/15 02:54, , 16F
10/15 02:54, 16F
→
10/15 02:59, , 17F
10/15 02:59, 17F
→
10/15 02:59, , 18F
10/15 02:59, 18F
推
10/15 03:05, , 19F
10/15 03:05, 19F
→
10/15 03:06, , 20F
10/15 03:06, 20F
推
10/15 03:09, , 21F
10/15 03:09, 21F
→
10/15 03:09, , 22F
10/15 03:09, 22F
推
10/16 00:43, , 23F
10/16 00:43, 23F
→
10/16 00:44, , 24F
10/16 00:44, 24F
→
10/16 00:47, , 25F
10/16 00:47, 25F
→
10/16 00:48, , 26F
10/16 00:48, 26F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 8 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
