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

Question

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

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

问题的第 2 部分让我很困惑。我们得到了更多信息：整数代表薪水，这意味着它们都是正数，其中绝大多数都在 1,000,000 以下。显然，有了这些额外的信息，就可以编写一个在 O(n) 时间内解决原始问题的算法，但我一点也不知道这是怎么可能的。有任何想法吗？

我会发布我到目前为止所做的事情，但我无法提出任何建议。

Answer 1

您正在寻找一种选择算法，它选择k数组中的第 th 大元素。Wikipedia 文章给出了一个 O(n) 算法来执行此操作，该算法类似于快速排序，但不对整个数组进行排序，因此避免了 O(n*logn) 运行时。

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