合并排序的数组

Question

可能的重复:
合并两个排序列表
 N路合并的算法

给定k个排序的数组,每个长度为n,构造一个合并和排序的array.focus运行时间和空间复杂度.

来源:亚马逊采访问题.
有什么想法吗？谢谢

Answer 1

从每个数组中的第一个元素创建一个堆.从堆中弹出head元素,将其插入结果数组,然后从堆的头部来自数组中的下一个元素,并将其插入堆中.重复直到您使用所有数组.

@Michael McTiernan:不,你误解了.Null Set不建议将所有输入数组元素转储到堆上 - 这确实是非常低效的.Null Set提出的是构建一个只包含`k`元素的堆:它包含每个已排序数组的第一个(最小)元素.每个数组只有一个元素.从堆中删除最小元素(并将其发送到输出)时,将同一数组中的下一个元素添加到堆中并重建堆.这样堆的大小总是只有`k`. (6认同)
请注意,此解决方案是最佳的.假设你可以做得比O(n*logk(k))更好 - 在这种情况下你可以将每个数组拆分为n个排序大小为1的子数组,并对其进行排序,复杂度更高,然后为O(n*的log(n)).因为排序被证明是欧米茄(n*logn),所以你会感到矛盾. (5认同)
@Michael这基本上是一种合并排序.我刚刚将它扩展到合并两个以上的排序列表.堆的重点是它可以在次线性时间O(log(n))中找到更新的候选集的最小值.至少这是个主意. (4认同)
这不是非常低效,因为OP中描述的条件描述了合并方式,这是完成方式的一部分吗？想一想.您有一些已排序的数组,您将要合并到已排序的数组中.您已经拥有mergesort的条件.我不是想在你的想法中挑选漏洞,只是我只是在深入研究排序算法并尽可能多地学习. (3认同)