最近我参加了一个面试,面试官要求我“编写一个程序,从一个包含10亿个数字的数组中找出100个最大的数字”。
我只能给出一个蛮力解决方案,即以O(nlogn)时间复杂度对数组进行排序,并取最后100个数字。
Arrays.sort(array);
面试官正在寻找一个更好的时间复杂度,我尝试了几个其他的解决方案,但都没有回答他。有没有更好的时间复杂度解决方案?
最近我参加了一个面试,面试官要求我“编写一个程序,从一个包含10亿个数字的数组中找出100个最大的数字”。
我只能给出一个蛮力解决方案,即以O(nlogn)时间复杂度对数组进行排序,并取最后100个数字。
Arrays.sort(array);
面试官正在寻找一个更好的时间复杂度,我尝试了几个其他的解决方案,但都没有回答他。有没有更好的时间复杂度解决方案?
当前回答
你可以保留一个最大的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)个数字的文件。
您可以使用快速选择算法在(按顺序)索引[十亿-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)
这个问题只需一行c++代码就可以用N log(100)的复杂度(而不是N log N)来回答。
std::vector<int> myvector = ...; // Define your 1 billion numbers.
// Assumed integer just for concreteness
std::partial_sort (myvector.begin(), myvector.begin()+100, myvector.end());
最终答案将是一个向量,其中前100个元素保证是数组中最大的100个数字,而其余元素是无序的
c++ STL(标准库)对于这类问题非常方便。
注意:我并不是说这是最佳的解决方案,但它可以挽救你的面试。
一个非常简单的解决方案是遍历该数组100次。也就是O(n)
每次取出最大的数字(并将其值更改为最小值,以便在下一个迭代中看不到它,或者跟踪以前答案的索引(通过跟踪索引,原始数组可以有多个相同的数字))。经过100次迭代,就得到了最大的100个数字。
我对此的直接反应是使用堆,但有一种方法可以使用QuickSelect,而不需要在任何时候保留所有的输入值。
创建一个大小为200的数组,并用前200个输入值填充它。运行QuickSelect并丢弃低100个位置,留下100个空闲位置。读入接下来的100个输入值并再次运行QuickSelect。继续执行,直到以100个批次为单位运行整个输入。
最后是前100个值。对于N个值,您运行QuickSelect大约N/100次。每个快速选择的代价大约是某个常数的200倍,所以总代价是某个常数的2N倍。在我看来,输入的大小是线性的,不管我在这个解释中硬连接的参数大小是100。