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

Question

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

Answer 1

找出每台机器上k个最大的数字。o（n*对数（k））
合并结果（在中央服务器上，如果k不是很大，则可以在跨服务器集群的树层次结构中合并它们）。
更新：为了说明这一点，联合收割机步骤不是排序。你只需从结果中选出前k个数字。有很多方法可以有效地做到这一点。例如，可以使用堆来推每个列表的头。然后，可以从堆中移除头部，并将头部从元素所属的列表中推出来。这样做K次会给你一个结果。所有这些都是o（k*log（k））。