您将如何在O（n * log K）时间中对平均长度为K的n个排序列表进行排序？

您将如何在O（n * log K）时间中对平均长度为K的n个排序列表进行排序？

正如您对问题的评论中提到的那样，不可能使用O（nlog（k）），但此页面上有两种算法可以有效地完成您的任务；这是一个：

取每个列表的第一个元素并创建一个堆（大小为k）。d出最小的元素。从元素中找到数组（假设它来自列表编号i）。从列表i中取出下一个元素并将其推入堆中。对于合并列表中的每个元素，我们花费了log（k）时间。因此，时间复杂度为O（N* logk），其中N是所有K个列表中元素的总数。