你可以保留一个最大的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位计数器的哈希表中)。

I would find out who had the time to put a billion numbers into an array and fire him. Must work for government. At least if you had a linked list you could insert a number into the middle without moving half a billion to make room. Even better a Btree allows for a binary search. Each comparison eliminates half of your total. A hash algorithm would allow you to populate the data structure like a checkerboard but not so good for sparse data. As it is your best bet is to have a solution array of 100 integers and keep track of the lowest number in your solution array so you can replace it when you come across a higher number in the original array. You would have to look at every element in the original array assuming it is not sorted to begin with.

这个问题只需一行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(标准库)对于这类问题非常方便。

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

两个选择:

(1)堆(priorityQueue)

维护最小堆的大小为100。遍历数组。一旦元素小于堆中的第一个元素，就替换它。

InSERT ELEMENT INTO HEAP: O（log100）
compare the first element: O(1)
There are n elements in the array, so the total would be O(nlog100), which is O(n)

(2)映射-约简模型。

这与hadoop中的单词计数示例非常相似。 映射工作:计算每个元素出现的频率或次数。 减约:获取顶部K元素。

通常，我会给招聘人员两个答案。他们喜欢什么就给什么。当然，映射缩减编码会很费事，因为您必须知道每个确切的参数。练习一下也无妨。 祝你好运。

The simplest solution is to scan the billion numbers large array and hold the 100 largest values found so far in a small array buffer without any sorting and remember the smallest value of this buffer. First I thought this method was proposed by fordprefect but in a comment he said that he assumed the 100 number data structure being implemented as a heap. Whenever a new number is found that is larger then the minimum in the buffer is overwritten by the new value found and the buffer is searched for the current minimum again. If the numbers in billion number array are randomly distributed most of the time the value from the large array is compared to the minimum of the small array and discarded. Only for a very very small fraction of number the value must be inserted into the small array. So the difference of manipulating the data structure holding the small numbers can be neglected. For a small number of elements it is hard to determine if the usage of a priority queue is actually faster than using my naive approach.

I want to estimate the number of inserts in the small 100 element array buffer when the 10^9 element array is scanned. The program scans the first 1000 elements of this large array and has to insert at most 1000 elements in the buffer. The buffer contains 100 element of the 1000 elements scanned, that is 0.1 of the element scanned. So we assume that the probability that a value from the large array is larger than the current minimum of the buffer is about 0.1 Such an element has to be inserted in the buffer . Now the program scans the next 10^4 elements from the large array. Because the minimum of the buffer will increase every time a new element is inserted. We estimated that the ratio of elements larger than our current minimum is about 0.1 and so there are 0.1*10^4=1000 elements to insert. Actually the expected number of elements that are inserted into the buffer will be smaller. After the scan of this 10^4 elements fraction of the numbers in the buffer will be about 0.01 of the elements scanned so far. So when scanning the next 10^5 numbers we assume that not more than 0.01*10^5=1000 will be inserted in the buffer. Continuing this argumentation we have inserted about 7000 values after scanning 1000+10^4+10^5+...+10^9 ~ 10^9 elements of the large array. So when scanning an array with 10^9 elements of random size we expect not more than 10^4 (=7000 rounded up) insertions in the buffer. After each insertion into the buffer the new minimum must be found. If the buffer is a simple array we need 100 comparison to find the new minimum. If the buffer is another data structure (like a heap) we need at least 1 comparison to find the minimum. To compare the elements of the large array we need 10^9 comparisons. So all in all we need about 10^9+100*10^4=1.001 * 10^9 comparisons when using an array as buffer and at least 1.000 * 10^9 comparisons when using another type of data structure (like a heap). So using a heap brings only a gain of 0.1% if performance is determined by the number of comparison. But what is the difference in execution time between inserting an element in a 100 element heap and replacing an element in an 100 element array and finding its new minimum?

在理论层面:在堆中插入需要多少比较。我知道它是O(log(n))但常数因子有多大呢?我 在机器级别:缓存和分支预测对堆插入和数组中线性搜索的执行时间有什么影响? 在实现级别:库或编译器提供的堆数据结构中隐藏了哪些额外成本?

我认为，在人们试图估计100个元素堆和100个元素数组的性能之间的真正区别之前，这些都是必须回答的一些问题。所以做一个实验并测量真实的表现是有意义的。

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

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