寻找n²个隐式数字的中位数的O(n)算法

Question

问题：输入是一个不一定排序的序列 S=k1，k2，...，kn，其中包含 n 个任意数字。考虑形如 min{ki，kj} 的 n² 个数字的集合 C，其中 1<=i, j<=n 。请提供一个时间复杂度为 O(n)，空间复杂度为 O(n) 的算法来找到 C 的中位数。

迄今为止，通过检查不同集合 S 的 C，我发现 C 中 S 中最小数字的出现次数等于(2n-1)，第二小的数字的出现次数等于(2n-3)，以此类推，直到最大数字只有一次出现。

有没有办法利用这些信息找到 C 的中位数？

- ejf071189

---

类似答案：https://cs.stackexchange.com/questions/1914/to-find-the-median-of-an-unsorted-array - roottraveller

如果有一种有效的方法来做到这一点，那么对于快速排序来说，数据的中位数是理想的枢轴，这将使其变得更好。 - Abhishek Choudhary

@AbhishekChoudhary 好的，那么您在此发表评论的原因并不清楚，因为问题不是关于“实践”，而是关于O(n)，而这个问题的O(n)解决方案（请参见其中一个答案）似乎不适用于快速排序。 - Kelly Bundy

@KellyBundy 我在谷歌上搜索了线性时间中位数算法，然后出现了这个结果，所以我认为这是同一个问题，下面大多数答案也都是关于线性时间中位数算法的，而且用O(n)的解法来找到中位数适用于快速排序，我们使用中位数作为枢轴，从而确保最坏情况下的O(n log n)复杂度。 - Abhishek Choudhary

@AbhishekChoudhary 是的，那些答案是错误的。它们的作者没有理解问题。 - Kelly Bundy

Answer 1

有很多可能性，我喜欢的是Hoare的Select算法。基本思想类似于快速排序，不同之处在于递归时，只递归到包含你要查找的数字的分区。

举个例子，如果你想找出100个数字的中位数，你可以像快速排序一样对数组进行分区。你会得到两个分区——其中一个包含第50个元素。在那个分区中递归地进行选择。继续进行，直到分区只包含一个元素，这将是中位数（注意，你也可以为另一个元素做同样的操作）。

- Jerry Coffin

---

但是，如果C的大小基于原始序列S具有n个数字为n ^ 2，那么在C上执行的选择的运行时间不是O（n ^ 2）吗？ - ejf071189

抱歉——我没有仔细阅读问题。你是对的——这是针对正在搜索的项目数量而不是该集合中唯一项目数量的线性。 - Jerry Coffin

我不这么认为--select算法通过对元素进行分区来开始，这意味着要查看所有的N^2个元素。 - Jerry Coffin

很明显，实现这一目标所需的项数少于n/2，因此我们只需进行n/2次比较。实现这一目标所需的项数对应于i，因此S中的第i个元素等同于C的中位数。然后，我们可以在O(n)时间内运行S的选择以找到O(n)时间内的第i个元素，因此总运行时间为O(n)。 - ejf071189

@domen：没错。如果你真的需要O(n)，那么最好使用中位数算法（median of medians algorithm）（但要记住，为了防止极少出现的最坏情况，它平均速度较慢）。 - Jerry Coffin

Answer 2

是的，好谜题。我们可以根据你所说的线索找到中位数。

在C语言中，max(k)出现次数为1次，次高值的出现次数为3次，再次次高值的出现次数为5次，以此类推。

1. 如果我们对C中的元素进行排序，第m个最大数左侧的元素数量为m^2（奇数之和）

2. 我们感兴趣的数字（用于计算中位数），当n为奇数时为(n^2+1)/2=α，当n为偶数时，α1=n^2/2和α2=n^2/2+1，但α1=n^2/2永远不是平方数=>紧接在α1右侧的数字等于α1（前m个奇数之和是平方数）=>α1=α2。

3. 因此，关键是确定m，使得m^2（前m个奇数之和）仅比(n^2/2)略高。

4. 因此，关键是确定m=ceil(n/sqrt(2))，以及原始序列中的第m个最大数。（找第m个最大数还是第(n-m-1)个最小数是优化问题）。

5. 我们可以很容易地找到第m个最大数（只需从左边不断记录前m个最大的数），或者使用中位数算法以线性时间完成。

- Om Deshmane

Answer 3

维基百科上有一篇有关 选取算法 的好文章。如果您使用的是C++，STL包含一个 nth_element() 算法，在平均情况下具有线性时间。

- Blastfurnace

---

@thiagowfx：谢谢，那个SGI参考资料太老了。 - Blastfurnace