最近我参加了一个面试，面试官要求我“编写一个程序，从一个包含10亿个数字的数组中找出100个最大的数字”。
我只能给出一个蛮力解决方案，即以O(nlogn)时间复杂度对数组进行排序，并取最后100个数字。
Arrays.sort(array);
面试官正在寻找一个更好的时间复杂度，我尝试了几个其他的解决方案，但都没有回答他。有没有更好的时间复杂度解决方案?
当前回答
一个非常简单的解决方案是遍历该数组100次。也就是O(n)
每次取出最大的数字(并将其值更改为最小值，以便在下一个迭代中看不到它，或者跟踪以前答案的索引(通过跟踪索引，原始数组可以有多个相同的数字))。经过100次迭代，就得到了最大的100个数字。
其他回答
Time ~ O(100 * N)
Space ~ O(100 + N)
创建一个包含100个空槽的空列表 对于输入列表中的每个数字: 如果数字小于第一个，跳过 否则用这个数字代替它 然后，将数字通过相邻的交换;直到它比下一个小 返回列表
注意:如果log(input-list.size) + c < 100，那么最佳的方法是对输入列表进行排序，然后拆分前100项。
取十亿个数字中的前一百个，然后排序。现在只需遍历十亿，如果源数大于100中最小的数，则按排序顺序插入。你得到的结果更接近于O(n)除以集合的大小。
我对此的直接反应是使用堆，但有一种方法可以使用QuickSelect，而不需要在任何时候保留所有的输入值。
创建一个大小为200的数组，并用前200个输入值填充它。运行QuickSelect并丢弃低100个位置，留下100个空闲位置。读入接下来的100个输入值并再次运行QuickSelect。继续执行，直到以100个批次为单位运行整个输入。
最后是前100个值。对于N个值，您运行QuickSelect大约N/100次。每个快速选择的代价大约是某个常数的200倍，所以总代价是某个常数的2N倍。在我看来，输入的大小是线性的，不管我在这个解释中硬连接的参数大小是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)
求n个元素中最大的m个元素，其中n >>> m
最简单的解决方案，每个人都应该很明显，就是简单地做m次冒泡排序算法。
然后打印出数组的最后n个元素。
它不需要外部数据结构，并且使用了一种大家都知道的算法。
运行时间估计为O(m*n)。到目前为止最好的答案是O(nlog (m))，所以这个解决方案对于小m来说并不显着昂贵。
我并不是说这不能改进，但这是迄今为止最简单的解决方案。
