这个问题只需一行c++代码就可以用N log(100)的复杂度(而不是N log N)来回答。

 std::vector<int> myvector = ...; // Define your 1 billion numbers. 
                                 // Assumed integer just for concreteness 
 std::partial_sort (myvector.begin(), myvector.begin()+100, myvector.end());

最终答案将是一个向量，其中前100个元素保证是数组中最大的100个数字，而其余元素是无序的

c++ STL(标准库)对于这类问题非常方便。

注意:我并不是说这是最佳的解决方案，但它可以挽救你的面试。

从十亿个数字中找到前100个最好使用包含100个元素的最小堆。

首先用遇到的前100个数字对最小堆进行质数。Min-heap将前100个数字中最小的存储在根(顶部)。

现在，当你继续计算其他数字时，只将它们与根数(100中最小的数)进行比较。

如果遇到的新数字大于最小堆的根，则将根替换为该数字，否则忽略它。

作为在最小堆中插入新数字的一部分，堆中最小的数字将移到顶部(根)。

一旦我们遍历了所有的数字，我们将得到最小堆中最大的100个数字。

我意识到这被标记为“算法”，但会抛出一些其他选项，因为它可能也应该被标记为“面试”。

10亿个数字的来源是什么?如果它是一个数据库，那么“从表中按值顺序选择值desc limit 100”就可以很好地完成工作-可能有方言差异。

这是一次性的，还是会重复发生?如果重复，频率是多少?如果它是一次性的，数据在一个文件中，那么'cat srcfile | sort(根据需要选择)| head -100'将让你快速完成有偿工作，而计算机处理这些琐碎的琐事。

如果重复，你会建议选择任何合适的方法来获得初始答案并存储/缓存结果，这样你就可以连续地报告前100名。

Finally, there is this consideration. Are you looking for an entry level job and interviewing with a geeky manager or future co-worker? If so, then you can toss out all manner of approaches describing the relative technical pros and cons. If you are looking for a more managerial job, then approach it like a manager would, concerned with the development and maintenance costs of the solution, and say "thank you very much" and leave if that is the interviewer wants to focus on CS trivia. He and you would be unlikely to have much advancement potential there.

祝你下次面试好运。

这个问题只需一行c++代码就可以用N log(100)的复杂度(而不是N log N)来回答。

 std::vector<int> myvector = ...; // Define your 1 billion numbers. 
                                 // Assumed integer just for concreteness 
 std::partial_sort (myvector.begin(), myvector.begin()+100, myvector.end());

最终答案将是一个向量，其中前100个元素保证是数组中最大的100个数字，而其余元素是无序的

c++ STL(标准库)对于这类问题非常方便。

注意:我并不是说这是最佳的解决方案，但它可以挽救你的面试。

简单的解决方案是使用优先队列，将前100个数字添加到队列中，并跟踪队列中最小的数字，然后遍历其他10亿个数字，每当我们发现一个比优先队列中最大的数字大的数字时，我们删除最小的数字，添加新的数字，并再次跟踪队列中最小的数字。

如果这些数字是随机顺序的，这就很好了，因为当我们迭代10亿个随机数字时，下一个数字是目前为止最大的100个数字之一的情况是非常罕见的。但这些数字可能不是随机的。如果数组已经按升序排序，则始终向优先队列插入一个元素。

我们先从数组中选取100,000个随机数。为了避免可能很慢的随机访问，我们添加了400个随机组，每个组有250个连续的数字。通过这种随机选择，我们可以非常确定，剩下的数字中很少有进入前100位的，因此执行时间将非常接近于一个简单的循环，将10亿个数字与某个最大值进行比较。

你可以保留一个最大的100个数字的优先队列，遍历10亿个数字。每当遇到大于队列中最小数字(队列头)的数字时，删除队列头并将新数字添加到队列中。

用堆实现的优先级队列的插入+删除复杂度为O(log K).(其中K = 100，要查找的元素数量。N = 10亿，数组中元素的总数)。

在最坏的情况下，你得到十亿*log2(100)这比十亿*log2(十亿)对于O(N log N)基于比较的排序要好。

一般来说，如果你需要一组N个数字中最大的K个数字，复杂度是O(N log K)而不是O(N log N)，当K与N相比非常小时，这可能非常重要。

这种优先级队列算法的预期时间非常有趣，因为在每次迭代中可能会出现插入，也可能不会出现插入。

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

例如，假设这些数字是从{0,1}中均匀随机选择的，第(i-k)个数字(从i个数字中)的期望值为(i-k)/i，并且随机变量大于此值的概率为1-[(i-k)/i] = k/i。

因此，期望插入数为:

期望运行时间可表示为:

(k时间生成包含前k个元素的队列，然后是n-k个比较，以及如上所述的预期插入次数，每次插入的平均时间为log(k)/2)

注意，当N与K相比非常大时，这个表达式更接近于N而不是nlog K。这有点直观，就像在这个问题的情况下，即使经过10,000次迭代(与十亿次相比非常小)，一个数字被插入队列的机会也非常小。

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

或者如果它们呈递减的趋势，最大的100个数字中的大多数将会非常早，我们的最佳情况运行时间本质上是O(N + K log K)对于K比N小得多的K，它就是O(N)

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

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

例如，计数排序在数字很小的情况下表现良好。16位数字只需要2^16个计数器的数组。而不是实际展开到一个排序的数组，你可以扫描你建立的直方图作为计数排序的一部分。

在对数组进行直方图化之后，您可以快速回答任何顺序统计的查询，例如最大的99个数字，最大的200到100个数字)32位数字将计数分散到一个更大的数组或计数器哈希表中，可能需要16gib的内存(每个2^32个计数器4字节)。在真正的cpu上，可能会有很多TLB和缓存失误，不像2^16个元素的数组，L2缓存通常会命中。

类似地，Radix Sort可以在第一次传递后只查看顶部的桶。但常数因子仍然可能大于logk，这取决于K。

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

如果有更多的计数器，则可能需要64位计数器，初始化为零并随机访问需要占用两倍的内存。或者是少数溢出16或32位整数的计数器的哨兵值，以指示计数的其余部分在其他地方(在一个小字典中，例如映射到64位计数器的哈希表中)。