作者FRAXIS (喔喔)
看板Prob_Solve
標題Re: [問題] 給定n個排好序的整數陣列 找中位數
時間Tue Oct 14 20:08:49 2014
: ※ 引述《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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1413288532.A.2C4.html
1F：推 dreamoon: 並無法保證max_i或是min_i列至少有一列可以刪掉一半吧? 10/14 22:56
2F：→ dreamoon: (在不知道min和max實際上是全部的數第幾大的情況下) 10/14 22:56
3F：→ FRAXIS: min小於median且max大於median min_i和max_i刪除等量元素 10/14 23:57
4F：推 dreamoon: 那你怎麼知道min小於median? 10/15 01:11
5F：→ FRAXIS: 因為min小於所有列至少一半的元素 10/15 01:31
6F：推 dreamoon: 我好像想懂了，不過你說的少於一半的元素應該還不夠輕楚 10/15 01:52
7F：→ dreamoon: 因為雖然一剛開始是求中位數,但過程中會變得不一定是在 10/15 01:53
8F：→ dreamoon: 求中位數 10/15 01:54
9F：→ FRAXIS: max_i和min_i要刪除等量元素 中位數不變 10/15 02:27
10F：推 dreamoon: 這不太對吧...?max_i和min_i可能包含不同數目的數? 10/15 02:37
11F：→ FRAXIS: 刪除比較小的列的一半元素個數 只要有一個列變成一半就好 10/15 02:46
12F：推 dreamoon: 這樣的話複雜度還會是O(n lg^2 n)嘛? 10/15 02:50
13F：→ FRAXIS: 每回合至少有一列減半 所以只有O(n lg n)回合 10/15 02:53
14F：推 dreamoon: 似乎會耶! 10/15 02:53
15F：→ FRAXIS: 每回合O(lg n)時間 所以總共是O(n lg^2 n) 10/15 02:53
16F：→ dreamoon: 恩恩，這樣的話就比我原本想的容易實做了 10/15 02:54
17F：→ FRAXIS: 實作上的細節還有base case，有可能O(1)的列一切再切.. 10/15 02:59
18F：→ FRAXIS: 這方法應該也可以找第k大的數字 10/15 02:59
19F：推 dreamoon: 我認為只要改程max_i和min_i一律減半,並重新計算 10/15 03:05
20F：→ dreamoon: 下一個round要求的是第幾大的數,就可以計算任意第k大了 10/15 03:06
21F：推 dreamoon: 若是求中位數的話,當某列只剩一個數且又被選到 10/15 03:09
22F：→ dreamoon: 應該是可以直接丟掉 10/15 03:09
23F：推 esrever: 如果不用 binary search, 而是對那些無法直接和 MoM 比大 10/16 00:43
24F：→ esrever: 小的元素 (像是比那排的中位數小，那排中位數卻 > MoM) 10/16 00:44
25F：→ esrever: 遞迴算出中位數(並記錄每排有幾個比它大)，這樣我們就知 10/16 00:47
26F：→ esrever: 該往比 MoM 大的那邊還是小的那邊遞迴下去 10/16 00:48