: ※ 引述《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) 但是蛮复杂的）