问题：输入是（不一定排序）序列S = K1，K2，...，N的任意数的千牛。考虑形式分N²数字{き，KJ}，收集下1＆LT; = I，J＆LT; = N。 present的 O（N）时间和 O（N）空间算法找到C的中位数

Problem: input is a (not necessarily sorted) sequence S = k1, k2, ..., kn of n arbitrary numbers. Consider the collection C of n² numbers of the form min{ki,kj}, for 1 <=i, j<=n. Present an O(n) time and O(n) space algorithm to find the median of C.

到目前为止我通过检查下不同组小号的最小的数S中在C中的实例的数目等于（2n-1个），下一个最小号发现直到你只有数量最多的一个实例。

So far I've found by examining C for different sets S that the number of instances of the smallest number in S in C is equal to (2n-1), the next smallest number: (2n-3) and so on until you only have one instance of the largest number.

有没有办法使用此信息来查找C的中位数？

Is there a way to use this information to find the median of C?

推荐答案

有多种可能性。我喜欢的是霍尔的选择算法。其基本思想是类似于快速排序，除了当你递归，你只递归到，将举行数（S），你要寻找的分区。

There are a number of possibilities. One I like is Hoare's Select algorithm. The basic idea is similar to a Quicksort, except that when you recurse, you only recurse into the partition that will hold the number(s) you're looking for.

例如，如果你想要的100号的中位数，你会通过分割阵列，就像在快速排序开始。你会得到两个分区 - 其中一个含有50 日元素。递归执行你选择该分区。继续，直到你的分区只包含一个元素，这将是中位数（请注意，你可以为你所选择的另一个元素做相同的）。

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).