作者FRAXIS (喔喔)
看板Prob_Solve
标题[问题] 给定n个排好序的整数阵列 找中位数
时间Tue Oct 14 06:47:02 2014
问题：给定 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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1413240425.A.2B6.html
1F：推 springman: 感觉上有机会比 O(n^2) 小，只是还蛮复杂的。 10/14 08:54
2F：→ springman: 有空来想想程式要怎麽写好了。 10/14 08:56