Merge k Sorted Lists

Q: 合并 k 个有序链表的时间复杂度是多少？

使用最小堆，时间复杂度为 O(N log k) ，其中 N 是值的总数， k 是列表的数量。每个值都会入堆和出堆各一次，堆中最多保存 k 个元素。除输出外，额外空间复杂度为 O(k) 。

Q: 为什么不把所有值放在一起排序呢？

这是正确的，时间复杂度为 O(N log N) 。这种方法没有利用列表已经排好序这一点，因此每个值都要付出 log N 的代价，而堆只需要 log k ，并且这种方法需要一次将所有值都放在内存中。堆还可以合并以数据流形式到达的列表。

Q: 你能在不使用堆的情况下合并 k 个已排序的列表吗？

是的，采用分治法。用双列表合并将列表两两合并，然后再将结果两两合并，以此类推：共进行 log k 轮，每轮都会访问每个值一次，因此时间复杂度为 O(N log k) 。依次将列表合并到不断扩大的结果中会更慢，时间复杂度为 O(N·k) ，因为较早的值会在每次合并中再次复制。

困难堆链表

+10

你会得到 k 个整数列表，作为 lists 的各行。每行都按非递减顺序排列，各行长度可以不同，并且没有空行。

将它们合并为一个列表，其中包含所有行中的每个值，并按非递减顺序排列，然后返回该列表。一个值在某一行或多行中出现几次，就在结果中出现几次。

函数

mergeKLists(lists: integer-2d-array) → integer-array

listsinteger-2d-array: 按行排列的已排序列表，每行一个，长度可能不同
返回值integer-array: 将每一行中的所有值放入一个排序后的列表

约束条件

1 ≤ lists.length ≤ 10⁴
1 ≤ lists[i].length，并且所有行合计最多包含 10⁴ 个值
-10⁴ ≤ lists[i][j] ≤ 10⁴
每一行都按非递减顺序排列。

示例

输入: lists = [[2, 6, 9], [1, 4, 10], [3, 5]]
输出: [1, 2, 3, 4, 5, 6, 9, 10]
解释: 各行分别以 2、1 和 3 开头，所以 1 排在最前面。接下来，各行的首项分别是 2、4 和 3，所以接下来是 2，依此类推。第三行在 5 后就结束了，剩下 6、9 和 10。

输入: lists = [[5], [-2, 5, 7], [0, 5]]
输出: [-2, 0, 5, 5, 5, 7]
解释: 这 3 个 5 来自 3 行不同的数据，因此都保留。负数 -2 排在 0 前面。

进阶

找出包含每一行中一个值的最小范围 [a, b]。用行首元素构成的堆，再加上最大的行首元素，能否在 O(N log k) 时间内完成？

题解

每一行都已排序，因此最小的未使用值总是某一行的第一个未使用值，也就是该行的行首。每处理 N 个值中的一个，都要扫描所有 k 个行首，这需要 k 步。用一个存放各行行首的最小堆，可以在 O(log k) 时间内取出最小值，从而将总时间复杂度从 O(N·k) 降至 O(N log k)。

对每个值比较所有 k 个头

结果正确，但无法在最大的测试中运行完毕

思路

在每一行的开头保留一个索引 pos[r]。每一轮读取所有行的行首值，追加最小值，并将该行的索引向前移动：这就是归并排序中的归并步骤，只是从两个列表扩展到了 k 个列表。在第一个示例中，行首值起初是 2、1 和 3，因此先输出 1，第二行的行首值变为 4。

每个 N 个值都需要遍历全部 k 行。若有 10^4 行，且每行只有一个值，就需要检查 10^8 次。

算法

将每一行的 pos[r] = 0，并统计值的数量，即 N。
重复 N 次：查看每一行中 pos[r] 仍在范围内的行，并记下表头最小的那一行。
将该表头添加到结果中，并将该行的 pos 加 1。
返回结果。

def mergeKLists(lists):
    pos = [0] * len(lists)  # pos[r]: index of the first unused value in row r
    total = sum(len(row) for row in lists)
    merged = []
    for _ in range(total):
        best = -1  # the row whose head is the smallest so far
        for r in range(len(lists)):
            if pos[r] < len(lists[r]) and (best == -1 or lists[r][pos[r]] < lists[best][pos[best]]):
                best = r
        merged.append(lists[best][pos[best]])
        pos[best] += 1
    return merged

k 个头节点的最小堆

思路

每次取出后，只有一个头部会变化，但扫描会重新读取所有 k 个元素。最小堆会把最小的元素放在堆顶。给每个头部标记所属的行，这样弹出 (value, row) 后，你就知道该把哪一行的下一个值放入堆中。只要某一行还有剩余值，堆中就始终会为该行保留一个条目，因此堆顶就是尚未使用的最小值。

在第一个示例中，堆的初始值是 2、1 和 3。弹出 1，放入 4。弹出 2，放入 6。弹出 3，放入 5。弹出 4，放入 10。弹出 5：第三行的值已经全部取完，因此不放入任何值。弹出 6，放入 9，然后弹出 9 和 10。

每个值只进入和离开堆一次，而且堆中最多只有 k 个条目：总共进行 2N 次 O(log k) 操作。当 N = k = 10^4 时，操作次数少于 3 × 10^5。堆占用 O(k) 内存。

算法

对于每一行 r，将 (lists[r][0], r) 压入按值排序的最小堆。
当堆不为空时，弹出最小的数对 (value, r)，并将 value 添加到结果中。
如果第 r 行还有下一个值，就将它与 r 一起压入堆中。
堆为空后，返回结果。

import heapq


def mergeKLists(lists):
    # The heap holds one (value, row) pair per row that still has values: that row's head.
    heap = [(row[0], r) for r, row in enumerate(lists)]
    heapq.heapify(heap)
    nxt = [1] * len(lists)  # nxt[r]: index of row r's next value, not yet in the heap
    merged = []
    while heap:
        value, r = heapq.heappop(heap)  # the smallest head of all rows
        merged.append(value)
        if nxt[r] < len(lists[r]):
            heapq.heappush(heap, (lists[r][nxt[r]], r))  # row r's new head takes its place
            nxt[r] += 1
    return merged

易错点和边界情况

只推入值。弹出后，你无法判断应该推进哪一行。把行号和值一起存储。
误用了最大堆。C++ priority_queue 和 Rust BinaryHeap 会把最大值放在顶部；使用 greater<> 或 Reverse。
一开始就推入所有值。结果仍然有序，但堆会增长到 N 个条目，工作量也会变成 O(N log N)。
读取短行末尾之后的内容。在第一个示例中，第三行只有两个值，所以推入下一个值之前要先检查是否还有值。
丢弃重复值。第二个示例中的三个 5 是不同的值，都应该放入结果中。

常见问题3

合并 k 个有序链表的时间复杂度是多少？

使用最小堆，时间复杂度为 O(N log k)，其中 N 是值的总数，k 是列表的数量。每个值都会入堆和出堆各一次，堆中最多保存 k 个元素。除输出外，额外空间复杂度为 O(k)。

为什么不把所有值放在一起排序呢？

这是正确的，时间复杂度为 O(N log N)。这种方法没有利用列表已经排好序这一点，因此每个值都要付出 log N 的代价，而堆只需要 log k，并且这种方法需要一次将所有值都放在内存中。堆还可以合并以数据流形式到达的列表。

你能在不使用堆的情况下合并 k 个已排序的列表吗？

是的，采用分治法。用双列表合并将列表两两合并，然后再将结果两两合并，以此类推：共进行 log k 轮，每轮都会访问每个值一次，因此时间复杂度为 O(N log k)。依次将列表合并到不断扩大的结果中会更慢，时间复杂度为 O(N·k)，因为较早的值会在每次合并中再次复制。

def mergeKLists(lists):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

lists = [[2, 6, 9], [1, 4, 10], [3, 5]]

预期输出

[1, 2, 3, 4, 5, 6, 9, 10]