<分区>
Possible Duplicate:
Can you sort n integers in O(n) amortized complexity?
我必须编写一个算法，给定一个未排序的整数列表，返回“文件中至少超过文件中数字 90% 的最小数字”，如果不存在这样的数字，则返回 -1。很简单:我使用归并排序对列表进行排序，然后从 90% 的索引开始，寻找第一个数字大于它之前的数字。
问题的第 2 部分让我感到难过。我们得到了更多信息:整数代表薪水，这意味着它们都是正数，其中绝大多数都在 1,000,000 以下。显然，有了这些额外的信息，就可以编写一个在 O(n) 时间内解决原始问题的算法，但我一点也不知道这是怎么可能的。有什么想法吗？
我会发布我到目前为止所做的一切，但我无法想出任何东西。
最佳答案
您正在寻找 selection algorithm ，它选择数组中第 k 大的元素。维基百科文章给出了一个 O(n) 算法来执行此操作，它类似于快速排序，但不会对整个数组进行排序，从而避免了 O(n*logn) 运行时间。
如果元素都在一定范围内(例如在您的情况下为 1-1000000)，则另一种方法是使用 counting sort 对它们进行排序或 bucket sort在 O(n) 中，然后选择您需要的元素。由于在这种情况下，“绝大多数”元素都在 1000000 以下，而不是所有元素，您可以使用 1000001 个桶执行桶排序，并将最后一个桶用于 1000000 以上的所有元素。
关于algorithm - 在 O(n) 时间内计算第 90 个百分位数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13346754/