最近我参加了一个面试,面试官要求我“编写一个程序,从一个包含10亿个数字的数组中找出100个最大的数字”。

我只能给出一个蛮力解决方案,即以O(nlogn)时间复杂度对数组进行排序,并取最后100个数字。

Arrays.sort(array);

面试官正在寻找一个更好的时间复杂度,我尝试了几个其他的解决方案,但都没有回答他。有没有更好的时间复杂度解决方案?


当前回答

一个非常简单的解决方案是遍历该数组100次。也就是O(n)

每次取出最大的数字(并将其值更改为最小值,以便在下一个迭代中看不到它,或者跟踪以前答案的索引(通过跟踪索引,原始数组可以有多个相同的数字))。经过100次迭代,就得到了最大的100个数字。

其他回答

从十亿个数字中找到前100个最好使用包含100个元素的最小堆。

首先用遇到的前100个数字对最小堆进行质数。Min-heap将前100个数字中最小的存储在根(顶部)。

现在,当你继续计算其他数字时,只将它们与根数(100中最小的数)进行比较。

如果遇到的新数字大于最小堆的根,则将根替换为该数字,否则忽略它。

作为在最小堆中插入新数字的一部分,堆中最小的数字将移到顶部(根)。

一旦我们遍历了所有的数字,我们将得到最小堆中最大的100个数字。

首先取1000个元素并将它们添加到一个max堆中。现在取出前最多100个元素并将其存储在某个地方。现在从文件中选择接下来的900个元素,并将它们与最后100个最高的元素一起添加到堆中。

一直重复这个过程,从堆中取出100个元素,从文件中添加900个元素。

从100个元素中最后选出的100个元素将从10亿个数字中选出最大的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)

取十亿个数字中的前一百个,然后排序。现在只需遍历十亿,如果源数大于100中最小的数,则按排序顺序插入。你得到的结果更接近于O(n)除以集合的大小。

复杂度为O(N)

首先创建一个100个int的数组,将这个数组的第一个元素初始化为N个值的第一个元素, 用另一个变量CurrentBig来跟踪当前元素的索引

遍历N个值

if N[i] > M[CurrentBig] {

M[CurrentBig]=N[i]; ( overwrite the current value with the newly found larger number)

CurrentBig++;      ( go to the next position in the M array)

CurrentBig %= 100; ( modulo arithmetic saves you from using lists/hashes etc.)

M[CurrentBig]=N[i];    ( pick up the current value again to use it for the next Iteration of the N array)

} 

完成后,从CurrentBig中打印M数组100次模100:-) 对于学生:确保代码的最后一行在代码退出之前没有胜过有效数据