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

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

Arrays.sort(array);

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


当前回答

你可以在O(n)个时间内完成。只需遍历列表,并跟踪在任何给定点上看到的最大的100个数字,以及该组中的最小值。当你发现一个新的数字大于你的10个数字中的最小值,然后替换它并更新你的新的100的最小值(可能每次你都要花100的常数时间来确定,但这并不影响整体分析)。

其他回答

此代码用于在未排序数组中查找N个最大的数字。

#include <iostream>


using namespace std;

#define Array_Size 5 // No Of Largest Numbers To Find
#define BILLION 10000000000

void findLargest(int max[], int array[]);
int checkDup(int temp, int max[]);

int main() {


        int array[BILLION] // contains data

        int i=0, temp;

        int max[Array_Size];


        findLargest(max,array); 


        cout<< "The "<< Array_Size<< " largest numbers in the array are: \n";

        for(i=0; i< Array_Size; i++)
            cout<< max[i] << endl;

        return 0;
    }




void findLargest(int max[], int array[])
{
    int i,temp,res;

    for(int k=0; k< Array_Size; k++)
    {
           i=0;

        while(i < BILLION)
        {
            for(int j=0; j< Array_Size ; j++)
            {
                temp = array[i];

                 res= checkDup(temp,max);

                if(res == 0 && max[j] < temp)
                    max[j] = temp;
            }

            i++;
        }
    }
}


int checkDup(int temp, int max[])
{
    for(int i=0; i<N_O_L_N_T_F; i++)
    {
        if(max[i] == temp)
            return -1;
    }

    return 0;
}

这可能不是一个有效的方法,但可以完成工作。

希望这能有所帮助

你可以遍历这些数字,需要O(n)

只要发现一个大于当前最小值的值,就将新值添加到一个大小为100的循环队列中。

循环队列的最小值就是新的比较值。继续往队列中添加。如果已满,则从队列中提取最小值。

你可以保留一个最大的100个数字的优先队列,遍历10亿个数字。每当遇到大于队列中最小数字(队列头)的数字时,删除队列头并将新数字添加到队列中。

用堆实现的优先级队列的插入+删除复杂度为O(log K).(其中K = 100,要查找的元素数量。N = 10亿,数组中元素的总数)。

在最坏的情况下,你得到十亿*log2(100)这比十亿*log2(十亿)对于O(N log N)基于比较的排序要好。

一般来说,如果你需要一组N个数字中最大的K个数字,复杂度是O(N log K)而不是O(N log N),当K与N相比非常小时,这可能非常重要。


这种优先级队列算法的预期时间非常有趣,因为在每次迭代中可能会出现插入,也可能不会出现插入。

第i个数字插入队列的概率是一个随机变量大于同一分布中至少i- k个随机变量的概率(前k个数字自动添加到队列中)。我们可以使用顺序统计(见链接)来计算这个概率。

例如,假设这些数字是从{0,1}中均匀随机选择的,第(i-k)个数字(从i个数字中)的期望值为(i-k)/i,并且随机变量大于此值的概率为1-[(i-k)/i] = k/i。

因此,期望插入数为:

期望运行时间可表示为:

(k时间生成包含前k个元素的队列,然后是n-k个比较,以及如上所述的预期插入次数,每次插入的平均时间为log(k)/2)

注意,当N与K相比非常大时,这个表达式更接近于N而不是nlog K。这有点直观,就像在这个问题的情况下,即使经过10,000次迭代(与十亿次相比非常小),一个数字被插入队列的机会也非常小。

但是我们不知道数组的值是均匀分布的。它们可能趋向于增加,在这种情况下,大多数或所有数字将成为所见最大的100个数字集合的新候选数。这个算法的最坏情况是O(N log K)

或者如果它们呈递减的趋势,最大的100个数字中的大多数将会非常早,我们的最佳情况运行时间本质上是O(N + K log K)对于K比N小得多的K,它就是O(N)


脚注1:O(N)整数排序/直方图

计数排序或基数排序都是O(N),但通常有更大的常数因子,使它们在实践中比比较排序更差。在某些特殊情况下,它们实际上相当快,主要是对于窄整数类型。

例如,计数排序在数字很小的情况下表现良好。16位数字只需要2^16个计数器的数组。而不是实际展开到一个排序的数组,你可以扫描你建立的直方图作为计数排序的一部分。

在对数组进行直方图化之后,您可以快速回答任何顺序统计的查询,例如最大的99个数字,最大的200到100个数字)32位数字将计数分散到一个更大的数组或计数器哈希表中,可能需要16gib的内存(每个2^32个计数器4字节)。在真正的cpu上,可能会有很多TLB和缓存失误,不像2^16个元素的数组,L2缓存通常会命中。

类似地,Radix Sort可以在第一次传递后只查看顶部的桶。但常数因子仍然可能大于logk,这取决于K。

注意,每个计数器的大小足够大,即使所有N个整数都是重复的,也不会溢出。10亿略小于2^30,所以一个30位无符号计数器就足够了。32位有符号或无符号整数就可以了。

如果有更多的计数器,则可能需要64位计数器,初始化为零并随机访问需要占用两倍的内存。或者是少数溢出16或32位整数的计数器的哨兵值,以指示计数的其余部分在其他地方(在一个小字典中,例如映射到64位计数器的哈希表中)。

可能的改进。

如果文件包含十亿的数字,读取它可能会很长…

为了提高工作效率,你可以:

将文件分成n个部分,创建n个线程,让n个线程在各自的部分中寻找最大的100个数字(使用优先级队列),最后得到所有线程输出的最大的100个数字。 使用像hadoop这样的解决方案,使用集群来完成这样的任务。在这里,您可以进一步分割文件,并更快地输出10亿(或10^12)个数字的文件。

求n个元素中最大的m个元素,其中n >>> m

最简单的解决方案,每个人都应该很明显,就是简单地做m次冒泡排序算法。

然后打印出数组的最后n个元素。

它不需要外部数据结构,并且使用了一种大家都知道的算法。

运行时间估计为O(m*n)。到目前为止最好的答案是O(nlog (m)),所以这个解决方案对于小m来说并不显着昂贵。

我并不是说这不能改进,但这是迄今为止最简单的解决方案。