algorithm - 将k个未排序的列表合并为一个并排序，然后将它们分成k个排序的列表？

Question

假设我有 k 个未排序的列表，我想将它们合并到一个列表中，以便我可以对它们运行我的排序算法，然后我需要分离这个大的合并列表以获得 k 个排序的列表。我怎样才能跟踪哪个元素属于哪个列表，以便我可以正确地分离这个合并列表？需要在线性时间内完成

Answer 1

假设我们有 n 个元素

初始化:
为每个列表中的每个元素添加一个 int 说明它属于哪个列表。遍历所有 O(n)。

合并:
对于每个列表，转到其末尾并使其指向下一个列表的开头。总时间 O(n)。

休息:
创建 k 指针 - 新 k 列表的开始。
遍历排序后的列表，对于列表中的每个元素，将其复制到新的 k 列表 中它所属于的列表的末尾。
我们可以记住每个新列表的末尾，因此需要 O(1) 才能到达那里。所以总时间为 O(n)。

并将所有时间加在一起 ​​- O(n)。