这是一个面试问题。我的K机每一个都被连接到1中央机器。每一个在K机有4个字节的数字文件的数组。您可以使用任何数据结构来加载这些数据到内存在这些机器上，他们适应。数字是不能跨ķ机器唯一的。查找在全国所有K个机号的工会在K人数最多。什么是最快的，我可以做到这一点？

This is an interview question. I have K machines each of which is connected to 1 central machine. Each of the K machines have an array of 4 byte numbers in file. You can use any data structure to load those numbers into memory on those machines and they fit. Numbers are not unique across K machines. Find the K largest numbers in the union of the numbers across all K machines. What is the fastest I can do this?

推荐答案

更新：要分清楚，该组合的步骤是不是一个排序。你只是从结果挑选前k个数字。有许多方法可以有效地做到这一点。您可以使用堆例如，推动每个列表的头。然后，你可以删除堆头部，并从列表中的元素属于推头。这样做k次给你的结果。所有这一切都为O（K *日志（K））。

Update: to make it clear, the combine step is not a sort. You just pick the top k numbers from the results. There are many ways to do this efficiently. You can use a heap for example, pushing the head of each list. Then you can remove the head from the heap and push the head from the list the element belonged to. Doing this k times gives you the result. All this is O(k*log(k)).