合并K个排序列表：效率
我收到一份作业，要求我将总共有N个元素的K个排序列表有效地合并到一个排序列表中。我偶然发现的方法是使用最小堆对K列表中的元素进行排序，或者使用分而治之的方法（成对合并）。该线程中的注释表明，分而治之方法的时间复杂度为O（NK），而最小堆方法的时间复杂度为O（N log K），两者的空间复杂度相同。我还访问了许多其他线程，但我不能得到一个清晰的图片。
怀疑
- 许多其他网站告诉我们，两者都存在分歧
共有1个答案
该线程是关于一个K方式的合并。也就是说，您查看所有K列表的第一个值，然后从一个列表中提取一个元素并重复。
它是时间O（n K），因为对于每个n元素，您正在寻找K列表的最小值。
分割和合并对一组合并使用O（n），这将列表数量减半。因此，在log（K）合并之后，您将及时完成O（n log（K））。
min-heap类似于K-way合并，除了它只需要时间O（1）找到最小的元素和O（log（K））得到它。所以需要时间O（n log（K））。
最小堆是优先级队列的一种实现，因此它是相同的。
所有这些方法占用相同的空间，O（n）。
祝你好运，无论你选择哪一个！
-
LeetCode上说明的问题如下： 合并k个排序链表，并将其作为一个排序列表返回。分析并描述其复杂性。 例子： 输入：[1- 我能够通过131个测试案例中的129个，但在案例130中达到了“超出时间限制”。下面是我的实现。 有人能发现瓶颈吗？对提高时间复杂度有什么建议吗？ 我在没有使用的情况下遇到了超过时间限制的问题。测试用例130包含10,000个LinkedList。
-
我正试图想出一个分而治之的算法来合并j个排序列表和n个元素，但我被卡住了；我不知道如何把这个问题分成更小的子问题。我希望合并算法更高效，如下所示： 合并前两个列表；然后将结果列表与第三个列表合并；然后将结果列表与第四个列表合并，以此类推，该列表取O（j*jn）。
-
这不是经典的“合并两个排序”列表问题，这在线性时间内是相当微不足道的。 我想做的是合并两个对的列表，它们已经按排序，其中两个列表中都有具有相同的对象：这些对象应该合并（添加）它们的
-
我想写一个时间O（n*lgk）的算法，将k个排序数组合并成一个排序数组，其中n是所有输入数组的元素总数。 你能告诉我怎么做吗？ 编辑：我编写了以下算法： 你能告诉我这是否正确吗？
-
问题内容： 已关闭 。这个问题是基于观点的。它当前不接受答案。 想改善这个问题吗？ 更新问题，以便通过编辑此帖子以事实和引用的形式回答。 7年前关闭。 改善这个问题 我想将排序的列表合并到一个列表中。这个解决方案如何？我相信它运行时间为O（n）。有任何明显的缺陷，效率低下或样式问题吗？ 我真的不喜欢为“这是第一次迭代”设置标志并使用它来确保“最低”具有默认值的习惯用法。有没有更好的办法解决呢？ 注
-
以下是我在Leetcode上解决“合并两个排序列表”算法问题的代码： 我得到了一个运行时错误。但是我的代码有什么问题？