我有m个数组,每个数组的长度为n.每个数组都已排序.我想创建一个长度为m*n的单个数组,其中包含前面数组的所有值(包括重复值),已排序.我必须合并这些数组..
我认为最佳时间复杂度是m*n*log(m)
这是算法的草图..
我创建了一个lenth m的支持数组H,它包含每个数组的第一个元素的所有值.
然后我对这个数组(m log m)进行排序,并将min值移动到输出数组.
然后我将移动的值替换为下一个移动的值.实际上我不替换它,但我将其插入右侧(已排序)位置.我认为这需要记录.
我对所有m*n值重复这一点......因此m*n*log m
我的问题..你能想到一个更有效的算法吗？如果mnlogm实际上是最佳的,你至少可以想到一个更简单,更优雅的算法吗？
在我的算法类中,我被要求制作一个K-way合并算法,该算法O(nlogk)
在搜索之后我发现它可以通过制作ak长度优先级队列并将其与每个列表的第一个元素一起排队来完成.提取最小值,将其附加到结果并从已提取元素的列表中排队.我很困惑:
它如何知道特定列表何时耗尽,假设列表的元素小于其他列表中的每个其他元素？
如何知道元素是哪个列表(如果结构不用于定义)？
时间复杂度如何O(nlogk)？
编辑:
如果有人可以逐步记下算法会更有帮助,因为我已经读过的所有内容都在句子中并且很难理解它的方式,如果有人能够记下算法可能有助于理解.