求一组数中值的O（n）算法

Question

问题：输入是n个任意数的序列S=k1，k2，…，kn（不一定排序）。考虑形式为min{ki，kj}的n个数的集合C，对于1<；=i，j<；=n。提出一个O(n)时间和O(n)空间算法来找到C的中值

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

有没有办法用这些信息来求C的中值？

Answer 1

有很多可能性。我喜欢的是霍尔的Select算法。基本思想类似于快速排序，只是当您递归时，您只能递归到包含您要查找的数字的分区中。

例如，如果您想要100个数字的中间值，可以像在Quicksort中一样，首先对数组进行分区。您将得到两个分区——其中一个包含50^th元素。递归地在那个分区中执行您的选择。继续，直到分区只包含一个元素，这将是中间值（注意，您可以对所选的另一个元素执行相同的操作）。

Answer 2

是的，很好的拼图。我们可以从你说的话中找到中位数。

在C中，有1次出现max（k），3次出现次高，5次出现次高，以此类推

1. 如果我们对C的元素进行排序，则mth最高数左边的元素数是m^2（奇数和）

2. 我们感兴趣的数字（计算中位数） a、 如果n是奇数，则为（n^2+1）/2=alpha b、 如果n是偶数，则alpha1=n^2/2和alpha2=n^2/2+1 但是alpha1=n^2/2从来不是一个正方形的数字=>；紧靠alpha1右侧的数字等于alpha1（前m个奇数的和是正方形的）=>；alpha1=alpha2。

3. 所以它可以归结为确定m使得m^2（前m个奇数的和）刚好高于（n^2/2）

4. 所以它可以归结为确定m=上限（n/sqrt（2））和原始序列中的mth最高数。（无论是m th最高还是（n-m-1）th最低都是优化）。

5. 我们可以很容易地找到mth最高数（只需从左起注意m的第一个最大数）或使用中值算法在线性时间内完成它。

Answer 3

维基百科有一篇关于Selection algorithms的好文章。如果使用C++，STL平均包含一个线性时间为{a2}的算法。