我做了我自己的代码，不确定它是否是“面试官”所寻找的

private static final int MAX=100;
 PriorityQueue<Integer> queue = new PriorityQueue<>(MAX);
        queue.add(array[0]);
        for (int i=1;i<array.length;i++)
        {

            if(queue.peek()<array[i])
            {
                if(queue.size() >=MAX)
                {
                    queue.poll();
                }
                queue.add(array[i]);

            }

        }

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

The description is quite general so maybe you can ask him the range or meaning of these numbers to make the problem clear. Doing this may impress an interviewer. If, for example, these numbers stands for people's age then it's a much easier problem. With a reasonable assumption that nobody alive is older than 200, you can use an integer array of size 200 (maybe 201) to count the number of people with the same age in just one iteration. Here the index means the age. After this it's a piece of cake to find 100 largest numbers. By the way this algorithm is called counting sort.

无论如何，让问题更具体、更清楚对你在面试中是有好处的。

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个元素数组的性能之间的真正区别之前，这些都是必须回答的一些问题。所以做一个实验并测量真实的表现是有意义的。

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

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

虽然其他的quickselect解决方案已经被否决，但事实是quickselect将比使用大小为100的队列更快地找到解决方案。在比较方面，Quickselect的预期运行时间为2n + o(n)。一个非常简单的实现是

array = input array of length n
r = Quickselect(array,n-100)
result = array of length 100
for(i = 1 to n)
  if(array[i]>r)
     add array[i] to result

这平均需要3n + o(n)次比较。此外，quickselect将数组中最大的100个项保留在最右边的100个位置，这可以提高效率。所以实际上，运行时间可以提高到2n+o(n)。

有一个问题是，这是预期的运行时间，而不是最坏的情况，但通过使用一个不错的主元选择策略(例如，随机选择21个元素，并选择这21个元素的中位数作为主元)，那么比较的数量可以保证高概率为(2+c)n对于任意小的常数c。

事实上，通过使用优化的抽样策略(例如随机抽样平方根(n)个元素，并选择第99百分位数)，对于任意小的c(假设K，要选择的元素数量为o(n))，运行时间可以降至(1+c)n + o(n)。

另一方面，使用大小为100的队列将需要O(log(100)n)个比较，log以2为底100的对数大约等于6.6。

如果我们从更抽象的意义上考虑这个问题，即从大小为N的数组中选择最大的K个元素，其中K=o(N)，但K和N都趋于无穷大，那么快速选择版本的运行时间将是o(N)，队列版本的运行时间将是o(N log K)，因此在这种意义上，快速选择也渐近地更好。

在注释中，提到队列解决方案将在随机输入的预期时间N + K log N内运行。当然，随机输入假设永远不会成立，除非问题明确地说明了这一点。队列解决方案可以以随机顺序遍历数组，但这将产生对随机数生成器的N次调用的额外成本，以及排列整个输入数组或分配一个长度为N的包含随机索引的新数组。

如果问题不允许您移动原始数组中的元素，并且分配内存的成本很高，因此不能复制数组，那就是另一回事了。但严格地从运行时间来看，这是最好的解决方案。

两个选择:

(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元素。

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