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

Question

最近在一次面试中，我被问到了这个问题：

将每个大小为n的k个排序数组合并成一个数组，使时间复杂度最小。

我提供了一个解决方案，使用大小为k的最小堆来查找k个列表顶部元素的最小值。

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

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

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

- Arpit Aggarwal

---

对于比较排序来说，这是不可能的。否则，你可以使用计数排序或桶排序（例如）。 - Thomas Mueller

@shx2 我同意你的答案，但既然面试官问了我这个问题，我还在等待更多的回答/评论。 - Arpit Aggarwal

不确定它是否仍然相关，我认为面试官可能混淆了 n。他很有可能认为 n 是所有 k 个列表中元素的数量；而在描述问题时，他提到 n 是每个列表的长度。 - Sidmeister

Answer 1

他错了，你是对的。或者这可能是一个诡计性问题。

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

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

当然，每个单例数组都已经按顺序排好了。时间复杂度：O(K)用于构建单例数组，O(K*1)用于合并（根据我们反驳的假设）。

- shx2

---

他也给了我一个提示。他说，如果所有的数组都是可变长度的，即k个数组中有N个元素。他说，在这种情况下，时间复杂度将为O(Nlogk)。他进一步说，由于你有一个放宽条件，即所有的数组都是固定大小n，你可以从中获得一些好处，并用更少的比较来解决问题。 - Arpit Aggarwal

@ArpitAggarwal，我不确定你的意思，但如果元素的总数是N*K，则最佳复杂度为O（NKlogK），而不是O（NK）。如果是N，则最佳复杂度为O（NlogK），而不是O（N）。关于放松，他是错的，因为我的答案证明了这一点。 - shx2

Answer 2

尽管您说的对，任何比较排序的下限都是n*log(n)（其中n是数组的大小），但有些排序算法可以用更短的时间完成。

由于您有k个已排序的列表，因此很容易找到您想要在最后得到的列表中的最小值（称为m）和最大值（称为M）。现在您知道需要排序的每个元素都在m和M之间。因此，您可以使用计数排序，它需要线性时间。[https://en.wikipedia.org/wiki/Counting_sort]

因此，查找m和M需要O(k)的时间，然后对数组进行排序需要O(n*k)的时间。因此，整个算法将需要O(nk)的时间。

- Array_sorter

---

它不是O(nk)，而是O(nk*(M-m))。对于像 [ [0], [9999999999999] ] 这样非常短的输入，它的表现如何？问题中没有任何指示表明您可以对值做出任何假设。此外，它仅适用于整数值。问题没有说明。如果它们是浮点数呢？ - shx2