这是一个面试问题。我有K台计算机,每台计算机都连接到1台中央计算机。K台机器中的每台机器在文件中都有4个字节数字的数组。您可以使用任何数据结构将这些数字加载到这些计算机上的内存中,并且它们适合。数字在K台机器上不是唯一的。在所有K台计算机的数字并集中找到K个最大数字。我最快能做到这一点?
更新:明确地说,合并步骤不是一种排序。您只需从结果中选择前k个数字。有很多方法可以有效地做到这一点。您可以使用堆,例如,推入每个列表的开头。然后,您可以从堆中删除头部,并从元素所属的列表中将其推入。这样做k次即可得到结果。这都是O(k * log(k))。