作者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/cn.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