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

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

Arrays.sort(array);

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


当前回答

Time ~ O(100 * N)
Space ~ O(100 + N)

创建一个包含100个空槽的空列表 对于输入列表中的每个数字: 如果数字小于第一个,跳过 否则用这个数字代替它 然后,将数字通过相邻的交换;直到它比下一个小 返回列表


注意:如果log(input-list.size) + c < 100,那么最佳的方法是对输入列表进行排序,然后拆分前100项。

其他回答

Time ~ O(100 * N)
Space ~ O(100 + N)

创建一个包含100个空槽的空列表 对于输入列表中的每个数字: 如果数字小于第一个,跳过 否则用这个数字代替它 然后,将数字通过相邻的交换;直到它比下一个小 返回列表


注意:如果log(input-list.size) + c < 100,那么最佳的方法是对输入列表进行排序,然后拆分前100项。

我知道这可能会被埋没,但这是我对一个基MSD的变化的想法。

伪代码:

//billion is the array of 1 billion numbers
int[] billion = getMyBillionNumbers();
//this assumes these are 32-bit integers and we are using hex digits
int[][] mynums = int[8][16];

for number in billion
    putInTop100Array(number)

function putInTop100Array(number){
    //basically if we got past all the digits successfully
    if(number == null)
        return true;
    msdIdx = getMsdIdx(number);
    msd = getMsd(number);
    //check if the idx above where we are is already full
    if(mynums[msdIdx][msd+1] > 99) {
        return false;
    } else if(putInTop100Array(removeMSD(number)){
        mynums[msdIdx][msd]++;
        //we've found 100 digits here, no need to keep looking below where we are
        if(mynums[msdIdx][msd] > 99){
           for(int i = 0; i < mds; i++){
              //making it 101 just so we can tell the difference
              //between numbers where we actually found 101, and 
              //where we just set it
              mynums[msdIdx][i] = 101;
           }
        }
        return true;
    }
    return false;
}

函数getMsdIdx(int num)将返回最高位(非零)的下标。函数getMsd(int num)将返回最高位。函数removeMSD(int num)将从一个数字中删除最有效的数字并返回该数字(如果删除最有效的数字后什么都没有留下,则返回null)。

完成后,剩下的就是遍历mynums以获取前100位数字。这大概是这样的:

int[] nums = int[100];
int idx = 0;
for(int i = 7; i >= 0; i--){
    int timesAdded = 0;
    for(int j = 16; j >=0 && timesAdded < 100; j--){
        for(int k = mynums[i][j]; k > 0; k--){
            nums[idx] += j;
            timesAdded++;
            idx++;
        }
    }
}

我需要注意的是,尽管上面的图看起来时间复杂度很高,但实际上它只有O(7*100)左右。

快速解释一下这是为了做什么: 从本质上讲,这个系统试图基于数字中数字的索引和数字的值来使用2d数组中的每个数字。它使用这些值作为索引来跟踪数组中插入了多少数值。当达到100时,它会关闭所有“较低的分支”。

这个算法的时间大概是O(十亿*log(16)*7)+O(100)。我可能是错的。此外,这很可能需要调试,因为它有点复杂,我只是把它写在我的头上。

编辑:没有解释的反对票是没有帮助的。如果你认为这个答案不正确,请留下评论。我很确定,StackOverflow甚至告诉你这样做,当你向下投票。

复杂度为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:-) 对于学生:确保代码的最后一行在代码退出之前没有胜过有效数据

您可以使用快速选择算法在(按顺序)索引[十亿-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)

虽然其他的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的包含随机索引的新数组。

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