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

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.

祝你下次面试好运。

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

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

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

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

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

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

您可以使用快速选择算法在(按顺序)索引[十亿-101]处查找数字 然后遍历这些数字找出比这个数字更大的数。

array={...the billion numbers...} 
result[100];

pivot=QuickSelect(array,billion-101);//O(N)

for(i=0;i<billion;i++)//O(N)
   if(array[i]>=pivot)
      result.add(array[i]);

该算法时间为:2 X O(N) = O(N)(平均情况性能)

Thomas Jungblut建议的第二个选择是:

使用堆构建最大堆将花费O(N)，然后前100个最大的数字将在堆的顶部，所有你需要的是把它们从堆(100 X O(Log(N))。

该算法时间为:O(N) + 100 X O(Log(N)) = O(N)

这个问题只需一行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次。也就是O(n)

每次取出最大的数字(并将其值更改为最小值，以便在下一个迭代中看不到它，或者跟踪以前答案的索引(通过跟踪索引，原始数组可以有多个相同的数字))。经过100次迭代，就得到了最大的100个数字。

使用第n个元素得到第100个元素O(n) 迭代第二次，但只有一次，并输出大于此特定元素的所有元素。

请特别注意，第二步可能很容易并行计算!当你需要一百万个最大的元素时，它也会很有效。