最近我参加了一个面试,面试官要求我“编写一个程序,从一个包含10亿个数字的数组中找出100个最大的数字”。
我只能给出一个蛮力解决方案,即以O(nlogn)时间复杂度对数组进行排序,并取最后100个数字。
Arrays.sort(array);
面试官正在寻找一个更好的时间复杂度,我尝试了几个其他的解决方案,但都没有回答他。有没有更好的时间复杂度解决方案?
最近我参加了一个面试,面试官要求我“编写一个程序,从一个包含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来说并不显着昂贵。
我并不是说这不能改进,但这是迄今为止最简单的解决方案。