以 O(nk) 的时间复杂度合并 k 个大小为 n 的排序数组

Question

最近在一次采访中我被问到这个问题：

以最小的时间复杂度将k 个排序的数组合并到一个大小为 n k 的数组中，每个数组都有 n 个元素。*

我给出了一个使用大小为 k 的 minheap 来找到 k 列表顶部元素的最小值的解决方案。

这样，时间复杂度将下降到 - O(nklogk)。

但他并不信服。他想要一个时间复杂度为 O(nk) 的解决方案。

我在互联网上搜索过，但找不到解决方案。

Answer 1

他是错的，你是对的。或许这是一个棘手的问题。

如果存在这样的解决方案，您可以在 O(K) 中对任何大小为 K 的数组进行排序，这已被证明是不可能的。

方法如下：您只需将大小为 K 的数组划分为 K 个单例数组，然后应用您的魔法函数。

当然，单例数组都是单独排序的。复杂度：O(K) 用于构建单例数组，O(K*1) 用于合并（根据我们反驳的假设）。