如果我有 K 个排序数组，每个数组有 N 个元素，例如
[0, 1, 2]
[1, 6, 8]
[10, 11, 12]
我知道我可以使用堆来合并它们，方法是循环所有列表及其元素并将它们插入堆中，然后每次都在 O(KN * log(KN)) 中取回最小值。
我在互联网上查了一下，另一种流行的解决方案似乎是使用仅包含 K 个元素的最小堆，并将 K 个列表的所有第一项插入堆中，然后取出最小值并将指针推进到该列表拥有那个最小元素。
除了更高效的内存需求(在第二种情况下为 O(K))，第二种方法在时间方面是否更高效？
可选的加分项:有没有比上述算法更好的算法？
最佳答案
第二个版本应该有 O(KN* log(K)) 的运行时间，因为您对每个元素 (N*K) 执行堆化 (log (K)) 操作。所以是的，它更快。我想不出更有效的方法来解决这个问题。
关于arrays - 合并 k 个排序数组 - 比较两个解决方案，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47676497/