问题：输入是一个（不一定是排序的）序列 S = k1, k2, ..., kn，由 n 个任意数字组成。考虑 min{ki,kj} 形式的 n² 个数的集合 C，其中 1 O(n)时间和O(n)空间算法求 C 的中位数。
到目前为止，我通过检查 C 的不同集合 S 发现，C 中 S 中最小数字的实例数等于 (2n-1)，下一个最小数字：(2n-3) 等等，直到你只有一个最大数字的实例。
有没有办法利用这些信息来找到 C 的中位数？
有多种可能性。我喜欢的一款是霍尔的Select算法。基本思想类似于快速排序，不同之处在于，当您递归时，您仅递归到保存您要查找的数字的分区。
For example, if you want the median of 100 numbers, you'd start by partitioning the array, just like in Quicksort. You'd get two partitions -- one of which contains the 50th element. Recursively carry out your selection in that partition. Continue until your partition contains only one element, which will be the median (and note that you can do the same for another element of your choice).
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
