※ 引述《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)快的方法来解决这问题呢？
应该很难吧！
资料有 n^2 笔，然后时间复杂度是 O(n^2)，基本上已经是 linear time
要低于线性时间
要嘛略过一些资料
要嘛问题本身有很强的数学性质，可以直接推导答案
在这个问题当中，上面两种策略似乎都行不太通
考虑 median-of-median algorithm 的第一回合
由于给定资料是 n 条已排序阵列，所以第一回合可以省下很多工夫，可以很快做完
但是找到中位数的中位数之后
接下来，还有可能是中位数的资料，约占全部的3/4
第二回合还是得处理 3/4 * n^2 这么多资料，依旧是 O(n^2) 级别
即便我们已经知道 n 条已排序阵列，但是它的功效只能帮助我们略过 1/4 的资料
再加上中位数没有什么好的数学性质，尤其是可以用于精确计算的的数学性质
所以我觉得很难达成！

其实就是用 median of median 的算法，只是找到median of median m 之后，用 binary search 找出每个排序的阵列中有几个元素比 m 小，看看要找的median 比 m 大还是比 m 小。虽然每次可能只能减少 1/4 的元素，不过没关系。每次花的时间，理论值是 O(n) 找 median of medianO(n log n) 找比 m 小的元素个数。总共应该只需要花 O(log n) 次每次都要使用排序好的阵列。

可是 problem size 不是 n^2 吗？这样上面的 n 都要换成 n^2

因为 n 个 size 为 n 的数列已经排序好了要算有几个元素比 m 小时，并不是拿 n^2 个元素来比较而是去每个数列做 binary search，所以时间是 O(nlogn)

第二回合要怎么找median of median?

每一个数列是哪个范围的元素在候选名单中需要记下来候选范围的资料的 median 同样可以找 median。

其实找median of median可以用排序 不影响复杂度但是会比较容易作

应该是不得不排序 为了知道“减少1/4的元素”来自哪些阵列springman的方法看起来可行 是O(n logn logn)

但是要怎么证明一次可以删除O(n/4)个元素？因为到最后每一列的元素都不一样多 原本median of median的证明法好像不能直接套用