在 O(n) 时间内计算第 90 个百分位数

Question

可能重复：
你能以 O(n) 摊余复杂度对 n 个整数进行排序吗？

我必须编写一个算法，给定一个未排序的整数列表，返回“文件中至少超过文件中数字 90% 的最小数字”，如果不存在这样的数字，则返回 -1。足够简单：我使用合并排序对列表进行排序，然后从 90% 的索引开始，查找第一个数字大于它之前的数字。

问题的第二部分让我难住了。我们得到了更多信息：整数代表工资，这意味着它们都是正数，而且绝大多数都在 1,000,000 以下。显然有了这些额外的信息，就可以编写一个在 O(n) 时间内解决原始问题的算法，但我完全不知道这是如何实现的。有什么想法吗？

我会发布到目前为止我所做的事情，但我还没有想出任何东西。

Answer 1

您正在寻找一种选择算法，它选择数组中第

k

最大的元素。维基百科文章给出了一个 O(n) 算法来执行此操作，该算法类似于快速排序，但不会对整个数组进行排序，从而避免了 O(n*logn) 运行时间。

如果元素都在一定范围内（例如您的情况为 1-1000000），则另一种方法是使用 计数排序 或 桶排序 在 O(n) 中对它们进行排序，然后选择您想要的元素需要。由于在这种情况下，“绝大多数”元素都在 1000000 以下，而不是全部，因此您可以使用 1000001 个存储桶执行存储桶排序，并对所有高于 1000000 的元素使用最后一个存储桶。