algorithm - O(n) 算法找到 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 的中位数？

Answer 1

有多种可能性。我喜欢的一个是 HoareSelect算法。基本思想类似于快速排序，除了当你递归时，你只递归到将保存你正在寻找的数字的分区。

例如，如果您想要 100 个数字的中位数，您可以从对数组进行分区开始，就像在快速排序中一样。你会得到两个分区——其中一个包含第 50^个元素。在该分区中递归执行您的选择。继续，直到您的分区仅包含一个元素，这将是中位数（请注意，您可以对您选择的另一个元素执行相同的操作）。

Answer 2

是的，很好的拼图。我们可以在你所说的线上找到中位数。

在 C 中，我们有 1 次出现 max(k)，3 次出现次高，5 次出现次高，依此类推

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

2. 我们感兴趣的数字（计算中位数）如果 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=ceiling(n/sqrt(2) 和原始序列中的第 m 个最高数。（是否找到第 m 个最高或 (nm-1) 个最低是优化）。

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

Answer 3

维基百科有一篇关于选择算法的好文章。如果您使用的是 C++，STL 包含一个nth_element()算法，平均而言是线性时间。