本文翻译自：Write a program to find 100 largest numbers out of an array of 1 billion numbers

I recently attended an interview where I was asked "write a program to find 100 largest numbers out of an array of 1 billion numbers." 我最近参加了一次采访，我被问到“编写一个程序，从10亿个数字中找出100个最大的数字。”

I was only able to give a brute force solution which was to sort the array in O(nlogn) time complexity and take the last 100 numbers. 我只能给出一个强力解决方案，即以O（nlogn）时间复杂度对数组进行排序并获取最后100个数字。

Arrays.sort(array);

The interviewer was looking for a better time complexity, I tried a couple of other solutions but failed to answer him. 面试官正在寻找更好的时间复杂性，我尝试了其他一些解决方案但未能回答他。 Is there a better time complexity solution? 有更好的时间复杂度解决方案吗？

---

#1楼

参考：https://stackoom.com/question/1Ig0A/编写一个程序-从-亿个数字的数组中找出-个最大的数字

---

#2楼

You can iterate over the numbers which takes O(n) 你可以迭代O（n）的数字

Whenever you find a value greater than the current minimum, add the new value to a circular queue with size 100. 只要找到大于当前最小值的值，就将新值添加到大小为100的循环队列中。

The min of that circular queue is your new comparison value. 该循环队列的最小值是您的新比较值。 Keep on adding to that queue. 继续添加到该队列。 If full, extract the minimum from the queue. 如果已满，请从队列中提取最小值。

---

#3楼

You can keep a priority queue of the 100 biggest numbers, iterate through the billion numbers, whenever you encounter a number greater than the smallest number in the queue (the head of the queue), remove the head of the queue and add the new number to the queue. 每当遇到大于队列中最小数字（队列头部）的数字时，您可以保留100个最大数字的优先级队列，遍历十亿个数字，删除队列的头部并添加新的数字到队列。

EDIT: as Dev noted, with a priority queue implemented with a heap, the complexity of insertion to queue is O(logN) 编辑：正如Dev所说，使用堆实现优先级队列，插入队列的复杂性为O(logN)

In the worst case you get billion log 2 (100) which is better than billion log 2 (billion) 在最坏的情况下，你得到billion log 2 (100) ，这比billion log 2 (billion)

In general, if you need the largest K numbers from a set of N numbers, the complexity is O(NlogK) rather than O(NlogN) , this can be very significant when K is very small comparing to N. 通常，如果您需要来自一组N个数字的最大K数，则复杂度为O(NlogK)而不是O(NlogN) ，当K与N相比非常小时，这可能非常重要。

EDIT2: EDIT2：

The expected time of this algorithm is pretty interesting, since in each iteration an insertion may or may not occur. 该算法的预期时间非常有趣，因为在每次迭代中，插入可能会也可能不会发生。 The probability of the i'th number to be inserted to the queue is the probability of a random variable being larger than at least iK random variables from the same distribution (the first k numbers are automatically added to the queue). 第i个数被插入队列的概率是随机变量大于来自相同分布的至少iK随机变量的概率（第一个k数被自动添加到队列中）。 We can use order statistics (see link ) to calculate this probability. 我们可以使用订单统计（参见链接 ）来计算这个概率。 For example, lets assume the numbers were randomly selected uniformly from {0, 1} , the expected value of (iK)th number (out of i numbers) is (ik)/i , and chance of a random variable being larger than this value is 1-[(ik)/i] = k/i . 例如，假设从{0, 1}均匀地随机选择数字，第（iK）个数字的期望值（i个数字中）是(ik)/i ，并且随机变量的概率大于此值为1-[(ik)/i] = k/i 。

Thus, the expected number of insertions is: 因此，预期的插入次数是：

And the expected running time can be expressed as: 预计运行时间可表示为：

( k time to generate the queue with the first k elements, then nk comparisons, and the expected number of insertions as described above, each takes an average log(k)/2 time) （ k生成具有前k元素的队列，然后是nk比较，以及如上所述的预期插入次数，每个采用平均log(k)/2时间）

Note that when N is very large comparing to K , this expression is a lot closer to n rather than NlogK . 请注意，当N与K相比非常大时，此表达式更接近n而不是NlogK 。 This is somewhat intuitive, as in the case of the question, even after 10000 iterations (which is very small comparing to a billion), the chance of a number to be inserted to the queue is very small. 这有点直观，就像在问题的情况下，即使在10000次迭代之后（与十亿次相比非常小），数字插入队列的可能性非常小。

---

#4楼

take the first 100 numbers of the billion and sort them. 取出十亿分之一的前100个数字并对它们进行排序。 now just iterate through the billion, if the source number is higher than the smallest of 100, insert in sort order. 现在只迭代十亿，如果源数高于100的最小值，则按排序顺序插入。 What you end up with is something much closer to O(n) over the size of the set. 你最终得到的是与集合大小相比更接近O（n）的东西。

---

#5楼

You can use Quick select algorithm to find the number at the(by order) index [billion-101] and then iterate over the numbers and to find the numbers that biger from that number. 您可以使用快速选择算法在（按顺序）索引[十亿-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]);

This algorithm Time is: 2 XO(N) = O(N) (Average case performance) 此算法时间为：2 XO（N）= O（N）（平均案例性能）

The second option like Thomas Jungblut suggest is: 像Thomas Jungblut这样的第二个选项建议是：

Use Heap building the MAX heap will take O(N),then the top 100 max numbers will be in the top of the Heap, all you need is to get them out from the heap(100 XO(Log(N)). 使用堆建设的最大堆需要O（N），那么前100最大的数字将在堆的顶部，所有你需要的是从堆取出来（100 XO（日志（N））。

This algorithm Time is:O(N) + 100 XO(Log(N)) = O(N) 该算法时间为：O（N）+ 100 XO（Log（N））= O（N）

---

#6楼

Although the other quickselect solution has been downvoted, the fact remains that quickselect will find the solution faster than using a queue of size 100. Quickselect has an expected running time of 2n + o(n), in terms of comparisons. 虽然另一个quickselect解决方案已被低估，但事实仍然是quickselect将比使用100号队列更快地找到解决方案。在比较方面，Quickselect的预期运行时间为2n + o（n）。 A very simply implementation would be 一个非常简单的实现将是

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

This will take 3n + o(n) comparisons on average. 这将平均进行3n + o（n）次比较。 Moreover, it can be made more efficient using the fact that quickselect will leave the largest 100 items in the array in the 100 right-most locations. 此外，使用quickselect将在最右边100个位置留下阵列中最大的100个项目这一事实可以提高效率。 So in fact, the running time can be improved to 2n+o(n). 所以事实上，运行时间可以提高到2n + o（n）。

There is the issue that this is expected running time, and not worst case, but by using a decent pivot selection strategy (eg pick 21 elements at random, and choose the median of those 21 as pivot), then the number of comparisons can be guaranteed with high probability to be at most (2+c)n for an arbitrarily small constant c. 问题在于这是预期的运行时间，而不是最坏的情况，但是通过使用适当的枢轴选择策略（例如，随机挑选21个元素，并选择那些21的中位数作为枢轴），那么比较的数量可以是对于任意小的常数c，保证最高概率为（2 + c）n。

In fact, by using an optimized sampling strategy (eg sample sqrt(n) elements at random, and choose the 99th percentile), the running time can be gotten down to (1+c)n + o(n) for arbitrarily small c (assuming that K, the number of elements to be selected is o(n)). 实际上，通过使用优化的采样策略（例如，随机采样sqrt（n）元素，并选择第99百分位数），运行时间可以降低到（1 + c）n + o（n）任意小的c （假设K，要选择的元素数是o（n））。

On the other hand, using a queue of size 100 will require O(log(100)n) comparisons, and log base 2 of 100 is approximately equal to 6.6. 另一方面，使用大小为100的队列将需要O（log（100）n）比较，并且100的log基数2约等于6.6。

If we think of this problem in the more abstract sense of choosing the largest K elements from an array of size N, where K=o(N) but both K and N go to infinity, then the running time of the quickselect version will be O(N) and the queue version will be O(N log K), so in this sense quickselect is also asymptotically superior. 如果我们从更大抽象意义上考虑这个问题，从大小为N的数组中选择最大的K元素，其中K = o（N）但K和N都变为无穷大，那么quickselect版本的运行时间将是O（N）和队列版本将是O（N log K），因此在这个意义上，quickselect也渐近优越。

In comments, it was mentioned that the queue solution will run in expected time N + K log N on a random input. 在评论中，有人提到队列解决方案将在随机输入的预期时间N + K log N上运行。 Of course, the random input assumption is never valid unless the question states it explicitly. 当然，除非问题明确说明，否则随机输入假设永远不会有效。 The queue solution could be made to traverse the array in a random order, but this will incur the additional cost of N calls to a random number generator as well as either permuting the entire input array or else allocating a new array of length N containing the random indices. 可以使队列解决方案以随机顺序遍历数组，但是这将导致对随机数生成器的N次调用的额外成本以及置换整个输入数组或者分配长度为N的新数组，其中包含随机指数。

If the problem doesn't allow you to move around the elements in the original array, and the cost of allocating memory is high so duplicating the array is not an option, that is a different matter. 如果问题不允许你移动原始数组中的元素，并且分配内存的成本很高，那么重复数组不是一个选项，这是另一回事。 But strictly in terms of running time, this is the best solution. 但严格来说，就运行时间而言，这是最好的解决方案。