如果在面试中被问到这个问题，面试官可能想看到你的解决问题的过程，而不仅仅是你对算法的了解。

这个描述比较笼统，所以你可以问他这些数字的范围或者含义，以便清楚地理解问题。这样做可能会给面试官留下好印象。例如，如果这些数字代表人的年龄，那么这是一个相对容易的问题。在合理假设没有人活得超过200岁的情况下，你可以使用一个大小为200（可能是201）的整数数组，在一次迭代中计算出拥有相同年龄的人数。这里的索引表示年龄。在这之后，找出前100个最大的数字就轻而易举了。顺便说一下，这个算法被称为计数排序。

总之，让问题更加具体和清晰对你在面试中是有好处的。

您可以保留一个最大值前100的优先队列，并迭代搜索十亿个数字。每当您遇到一个大于队列中最小的数字（队列头）时，删除队列头并将新数字添加到队列中。

使用堆实现的优先队列的插入和删除复杂度为O(log K)（其中K=100即要查找的元素数量，N=十亿个数字即数组中的总元素数量）。

在最坏情况下，您将获得十亿乘以log2(100)，这比使用O(NlogN)基于比较的排序十亿乘以log2(十亿)要好。

一般来说，如果您需要从N个数字中找出最大的K个数字，则复杂度为O(Nlog K)而不是O(Nlog N)。当K相对于N非常小时，这可能非常重要。

这个优先队列算法的期望时间非常有趣，因为在每次迭代中可能会插入或不插入。

第i个数字被插入队列的概率是随机变量大于相同分布的至少i-K个随机变量的概率（前k个数字自动添加到队列中）。我们可以使用顺序统计（见链接）来计算这个概率。

举例来说，假设数字从{0, 1}中以均匀随机方式选择，第第K个数字（共 i个数字）的期望值为(i-k)/i，随机变量大于此值的几率为1-[(i-k)/i] = k/i。

因此，预期插入次数为：

期望运行时间为：

（k次生成前k个元素的队列，然后n-k次比较，上文所述的预期插入次数每个需要平均log(k)/2时间）

需要注意的是，当N远大于K时，该表达式与N log K的差距很大。这在一定程度上是直观的，因为即使进行了10,000次迭代（相对于十亿来说非常小），插入队列的几率仍然非常小。

但我们不知道数组值是否均匀分布。它们可能趋向于增加，在这种情况下，大多数或全部数字将是有可能成为100个最大数字的新候选者。该算法的最坏情况为O(N log K)。

或者如果它们趋向于减少，大部分最大的100个数字将非常早地出现，我们的最佳情况运行时间基本上是O(N + K log K)，如果K比N小得多，则为O(N)。

注脚1：O(N)整数排序/直方图

计数排序或基数排序都是O(N)，但常数因子通常比实际上的比较排序更大。 在某些特殊情况下，它们实际上非常快，主要是针对狭窄的整数类型。

例如，如果数字很小，则计数排序会表现得很好。 16位数字只需要一个2 ^ 16个计数器数组。而且，你只需要扫描你构建的计数排序的直方图，而不必扩展回一个排序后的数组。

在直方图制作完毕之后，你可以快速地回答对于任何顺序统计量的查询，例如最大的99个数字，第100到第200大的数字。（译注：顺序统计量是一类在一列数字里面考虑顺序的统计，有媒体报道说顺序统计量是新时代算法升级的必选技能之一，此处只考察相关性而不作评价。）32位数字会在更大的数组或计数器的哈希表上分散计数，潜在地需要16GiB的内存（2 ^ 32个计数器的每个需要4字节）。 在现实的 CPU 上，可能会遇到很多 TLB 和缓存丢失，而不像一个2 ^ 16个元素的数组，其L2缓存通常会命中。

同样地，基数排序在第一次排序后可能只查看顶部的桶。 但常数因子可能仍然比log K要大，这取决于K。

请注意，每个计数器的大小足够大，即使所有N个整数都是重复的，也不会溢出。 十亿略低于2 ^ 30，因此30位无符号计数器就足够了。32位有符号或无符号整数也完全可以。

如果你有更多，可能需要64位计数器，这将使内存占用量翻倍以初始化为0并随机访问。 或者针对几个溢出16位或32位整数的计数器，使用哨兵值表示其余计数位于其他地方（在诸如映射到64位计数器的小字典（如哈希表）中）。