我最近参加了一次采访，当时我被要求“编写一个程序，从 10 亿个数字的数组中找出 100 个最大的数字”。
我只能给出一个蛮力解决方案，即以 O(nlogn) 时间复杂度对数组进行排序并取最后 100 个数字。
Arrays.sort(array);
面试官正在寻找更好的时间复杂度，我尝试了其他几个解决方案但未能回答他。有没有更好的时间复杂度解决方案？
您可以保留 100 个最大数字的优先级队列，遍历十亿个数字，每当遇到大于队列中最小数字（队列头）的数字时，删除队列头并添加新数字到队列。
编辑： 正如 Dev 所指出的，使用堆实现的优先级队列，插入队列的复杂性是O(log N)
O(log N)
在最坏的情况下，你会得到比billion*log2(100)``billion*log2(billion)
billion*log2(100)``billion*log2(billion)
一般来说，如果您需要一组 N 个数字中最大的 K 个数字，则复杂度是O(N log K)而不是O(N log N)，当 K 与 N 相比非常小时，这可能非常重要。
O(N log K)
O(N log N)
编辑2：
该算法的预期时间非常有趣，因为在每次迭代中可能会或可能不会发生插入。第 i 个数字插入队列的概率是随机变量至少大于i-K来自相同分布的随机变量的概率（前 k 个数字自动添加到队列中）。我们可以使用订单统计（见链接）来计算这个概率。例如，假设数字是从 中均匀随机选择的{0, 1}，第 (iK) 个数字（在 i 个数字中）的期望值为(i-k)/i，并且随机变量大于该值的机会为1-[(i-k)/i] = k/i。
i-K
{0, 1}
(i-k)/i
1-[(i-k)/i] = k/i
因此，预期的插入次数为：
并且预期的运行时间可以表示为：
（k生成具有第一个k元素的队列的时间，然后n-k是比较，以及如上所述的预期插入次数，每个都需要平均log(k)/2时间）
k
n-k
log(k)/2
请注意，当N与 相比非常大时K，此表达式更接近于n而不是N log K。这有点直观，就像问题的情况一样，即使经过 10,000 次迭代（与十亿相比非常小），将一个数字插入队列的机会也非常小。
N
K
n
N log K
