algorithm - 编写一个程序，从 10 亿个数字的数组中找出 100 个最大的数字

Question

我最近参加了一次采访，有人问我“编写一个程序，从 10 亿个数字中找出 100 个最大的数字”。

我只能给出一个蛮力解决方案，即以 O(nlogn) 时间复杂度对数组进行排序并取最后 100 个数字。

Arrays.sort(array);

面试官正在寻找更好的时间复杂度，我尝试了其他几种解决方案但未能回答他。有没有更好的时间复杂度解决方案？

Answer 1

你可以保留一个最大的 100 个数字的优先队列，遍历十亿个数字，当你遇到一个大于队列中最小数字(队列头)的数字时，移除队列的头部并添加新的数字到队列。
编辑:
正如 Dev 所指出的，使用堆实现的优先级队列，插入队列的复杂性是 O(log N)在最坏的情况下，您会得到 billion*log2(100)这比billion*log2(billion)更好
一般来说，如果你需要一组N个数字中最大的K个数字，复杂度为O(N log K)而不是 O(N log N) ，当 K 与 N 相比非常小时，这可能非常重要。
编辑2:
该算法的预期时间非常有趣，因为在每次迭代中可能会或可能不会发生插入。第 i 个数字插入队列的概率是随机变量至少大于 i-K 的概率。来自同一分布的随机变量(前 k 个数字会自动添加到队列中)。我们可以使用订单统计(见 link)来计算这个概率。例如，假设这些数字是从 {0, 1} 中均匀随机选择的。 ，第 (i-K) 个数字(在 i 个数字中)的期望值为 (i-k)/i ，并且随机变量大于该值的几率是 1-[(i-k)/i] = k/i .
因此，预期的插入次数是:

预期运行时间可以表示为:

( k 使用前 k 个元素生成队列的时间，然后是 n-k 比较，以及如上所述的预期插入次数，每个平均花费 log(k)/2 时间)
注意当 N与 K 相比非常大，这个表达式更接近 n而不是 N log K .这有点直观，因为在问题的情况下，即使经过 10,000 次迭代(与十亿次相比，这是非常小的)，将数字插入队列的机会也非常小。