编写一个程序,从10亿个数字的数组中找出100个最大的数字

Question

我最近参加了一次采访,我被问到"编写一个程序,从10亿个数字中找出100个最大的数字."

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

Arrays.sort(array);

面试官正在寻找更好的时间复杂性,我尝试了其他一些解决方案但未能回答他.有更好的时间复杂度解决方案吗？

Answer 1

每当遇到大于队列中最小数字(队列头部)的数字时,您可以保留100个最大数字的优先级队列,迭代十亿个数字,删除队列的头部并添加新的数字到队列.

编辑: 正如Dev所指出的,使用堆实现的优先级队列,插入队列的复杂性是O(logN)

在最糟糕的情况下,你会得到哪个更好billionlog2(100)billionlog2(billion)O(NlogK)

一般来说,如果你需要一组N个数中最大的K数,那么复杂性O(NlogN)不是i-K,当K与N相比非常小时,这可能非常重要.

EDIT2:

该算法的预期时间非常有趣,因为在每次迭代中,插入可能会也可能不会发生.第i个数字被插入队列的概率是随机变量大于至少{0, 1}来自相同分布的随机变量的概率(第一个k数被自动添加到队列中).我们可以使用订单统计(参见链接)来计算这个概率.例如,假设从中均匀地随机选择数字(i-k)/i,(iK)数的期望值(i个数之外)是1-[(i-k)/i] = k/i,并且随机变量大于该值的机会是k.

因此,预期的插入次数是:

预计运行时间可表示为:

(k生成具有第一个n-k元素的队列的时间,然后是log(k)/2比较,以及如上所述的预期插入次数,每个都需要平均N时间)

请注意,当K比较非常大时n,这个表达式更接近NlogK而不是O(logN).这有点直观,就像在问题的情况下,即使在10000次迭代之后(与十亿次相比非常小),数字插入队列的可能性非常小.

Answer 2

如果在面试中询问,我认为面试官可能希望看到你的问题解决过程,而不仅仅是你对算法的了解.

描述很一般,所以也许你可以问他这些数字的范围或含义,以使问题清楚.这样做可能会给面试官留下深刻印象.例如,如果这些数字代表一个国家(例如中国)的人口年龄,那么这是一个更容易解决的问题.假设没有人活着超过200,你可以使用大小为200(可能是201)的int数组来计算一次迭代中具有相同年龄的人数.这里的指数意味着年龄.在此之后,找到100个最大的数字是一块蛋糕.顺便说一句,这个算法被称为计数排序.

无论如何,让问题更具体,更清晰,对你来说是个好消息.

Answer 3

你可以迭代O(n)的数字

只要找到大于当前最小值的值,就将新值添加到大小为100的循环队列中.

该循环队列的最小值是您的新比较值.继续添加到该队列.如果已满,请从队列中提取最小值.

Answer 4

我意识到这是用'算法'标记的,但是会抛弃其他一些选项,因为它可能也应该标记为'面试'.

10亿个数字的来源是什么？如果它是一个数据库,那么'通过值desc limit 100从表顺序中选择值'可以很好地完成工作 - 可能存在方言差异.

这是一次性的,还是会重复的？如果重复,多久一次？如果它是一次性的并且数据在文件中,那么'cat srcfile | 排序(根据需要选择)| head -100'会让你快速做有成效的工作,当你的计算机处理这个琐碎的家务时,你会得到报酬.

如果重复,你会建议采取任何体面的方法来获得初始答案并存储/缓存结果,这样你就可以连续报告前100名.

最后,还有这个考虑因素.您是在寻找一份入门级的工作,并与一位令人讨厌的经理或未来的同事面谈？如果是这样,那么你可以抛弃描述相关技术优缺点的各种方法.如果你正在寻找一份更具管理性的工作,那么就像管理者那样接近它,关心解决方案的开发和维护成本,然后说"非常感谢"并离开,如果这是面试官想要专注于CS琐事.他和你在那里不太可能有太大的进步潜力.

在接下来的采访中祝你好运.

Answer 5

我对此的立即反应是使用堆,但是有一种方法可以使用QuickSelect,而无需在任何时候保留所有输入值.

创建一个大小为200的数组,并用前200个输入值填充它.运行QuickSelect并丢弃低100,留下100个空闲位置.读入接下来的100个输入值并再次运行QuickSelect.继续,直到您以100个批次运行整个输入.

最后,您有前100个值.对于N值,您大约运行QuickSelect N/100次.每个Quickselect的成本约为常量的200倍,因此总成本是某些常数的2N倍.这看起来与我输入的大小成线性关系,无论我在这个解释中硬接线为100的参数大小.

Answer 6

您可以使用快速选择算法在(按顺序)索引[十亿-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 XO(N)= O(N)(平均案例性能)

像Thomas Jungblut这样的第二个选择建议是:

使用堆建设的最大堆需要O(N),那么前100最大的数字将在堆的顶部,所有你需要的是从堆取出来(100 XO(日志(N)).

该算法时间为:O(N)+ 100 XO(Log(N))= O(N)

Answer 7

虽然另一个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的中位数作为枢轴),那么比较的数量可以是对于任意小的常数c,保证最高概率为(2 + c)n.

实际上,通过使用优化的采样策略(例如,随机采样sqrt(n)元素,并选择第99百分位数),运行时间可以降低到(1 + c)n + o(n)任意小的c (假设K,要选择的元素数是o(n)).

另一方面,使用大小为100的队列将需要O(log(100)n)比较,并且100的log基数2约等于6.6.

如果我们从更大抽象意义上考虑这个问题,从大小为N的数组中选择最大的K元素,其中K = o(N)但K和N都变为无穷大,那么quickselect版本的运行时间将是O(N)和队列版本将是O(N log K),因此在这个意义上,quickselect也渐近优越.

在评论中,有人提到队列解决方案将在随机输入的预期时间N + K log N上运行.当然,除非问题明确说明,否则随机输入假设永远不会有效.可以使队列解决方案以随机顺序遍历数组,但是这将导致对随机数生成器的N次调用的额外成本以及置换整个输入数组或者分配包含n的新长度N的数组.随机指数.

如果问题不允许你移动原始数组中的元素,并且分配内存的成本很高,那么复制数组不是一个选项,这是另一回事.但严格来说,就运行时间而言,这是最好的解决方案.

Answer 8

取出十亿分之一的前100个数字并对它们进行排序.现在只迭代十亿,如果源数高于100的最小值,则按排序顺序插入.你最终得到的是与集合大小相比更接近O(n)的东西.