一尘不染

查找存储在k台计算机上的k个数组中的最大k个数字

algorithm

这是一个面试问题。我有K台计算机,每台计算机都连接到1台中央计算机。K台机器中的每台机器在文件中都有4个字节数字的数组。您可以使用任何数据结构将这些数字加载到这些计算机上的内存中,并且它们适合。数字在K台机器上不是唯一的。在所有K台计算机的数字并集中找到K个最大数字。我最快能做到这一点?


阅读 233

收藏
2020-07-28

共1个答案

一尘不染

  • 在每台机器上找到k个最大的数字。O(n * log(k))
  • 合并结果(在集中式服务器上,如果k不大,否则可以将其合并到整个服务器群集中的树层次结构中)。

更新:明确地说,合并步骤不是一种排序。您只需从结果中选择前k个数字。有很多方法可以有效地做到这一点。您可以使用堆,例如,推入每个列表的开头。然后,您可以从堆中删除头部,并从元素所属的列表中将其推入。这样做k次即可得到结果。这都是O(k * log(k))。

2020-07-28