最近我参加了一个面试，面试官要求我“编写一个程序，从一个包含10亿个数字的数组中找出100个最大的数字”。
我只能给出一个蛮力解决方案，即以O(nlogn)时间复杂度对数组进行排序，并取最后100个数字。
Arrays.sort(array);
面试官正在寻找一个更好的时间复杂度，我尝试了几个其他的解决方案，但都没有回答他。有没有更好的时间复杂度解决方案?
当前回答
我做了我自己的代码，不确定它是否是“面试官”所寻找的
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]);
}
}
其他回答
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.
我对此的直接反应是使用堆，但有一种方法可以使用QuickSelect，而不需要在任何时候保留所有的输入值。
创建一个大小为200的数组，并用前200个输入值填充它。运行QuickSelect并丢弃低100个位置，留下100个空闲位置。读入接下来的100个输入值并再次运行QuickSelect。继续执行，直到以100个批次为单位运行整个输入。
最后是前100个值。对于N个值，您运行QuickSelect大约N/100次。每个快速选择的代价大约是某个常数的200倍，所以总代价是某个常数的2N倍。在我看来，输入的大小是线性的，不管我在这个解释中硬连接的参数大小是100。
首先取1000个元素并将它们添加到一个max堆中。现在取出前最多100个元素并将其存储在某个地方。现在从文件中选择接下来的900个元素，并将它们与最后100个最高的元素一起添加到堆中。
一直重复这个过程，从堆中取出100个元素，从文件中添加900个元素。
从100个元素中最后选出的100个元素将从10亿个数字中选出最大的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(标准库)对于这类问题非常方便。
注意:我并不是说这是最佳的解决方案，但它可以挽救你的面试。
使用第n个元素得到第100个元素O(n) 迭代第二次，但只有一次，并输出大于此特定元素的所有元素。
请特别注意，第二步可能很容易并行计算!当你需要一百万个最大的元素时，它也会很有效。
