我有m个数组,每个数组的长度为n.每个数组都已排序.我想创建一个长度为m*n的单个数组,其中包含前面数组的所有值(包括重复值),已排序.我必须合并这些数组..
我认为最佳时间复杂度是m*n*log(m)
这是算法的草图..
我创建了一个lenth m的支持数组H,它包含每个数组的第一个元素的所有值.
然后我对这个数组(m log m)进行排序,并将min值移动到输出数组.
然后我将移动的值替换为下一个移动的值.实际上我不替换它,但我将其插入右侧(已排序)位置.我认为这需要记录.
我对所有m*n值重复这一点......因此m*n*log m
我的问题..你能想到一个更有效的算法吗？如果mnlogm实际上是最佳的,你至少可以想到一个更简单,更优雅的算法吗？