合并k个有序数组

题目描述

给定 $k$ 个按非递减顺序排列的整数数组，将它们合并为一个非递减数组。要求保留所有元素及其出现次数，不修改输入数组，也不直接对全部元素调用排序函数。

数组和元素的下标均从0开始。允许负数、重复值、空数组以及长度不同的数组；当 $k=0$ 时返回空数组。记所有数组的元素总数为 $N$。

示例： 输入 [[1, 4, 7], [2, 5, 8], [0, 3, 6]]，输出 [0, 1, 2, 3, 4, 5, 6, 7, 8]。输入 [[], [2, 2], [-1]]，输出 [-1, 2, 2]。

本题承接合并排序：归并排序把一个无序数组拆分后排序，本题的每个输入数组已经有序，只需设计合并顺序。

题目分析

为什么按数组个数均衡划分

可以依次把下一个数组并入当前结果，但当前结果会越来越长。若 $k$ 个数组等长，反复扫描前面的元素会使总工作量达到 $O(Nk)$。

分治方法将数组列表分成左右两组，分别合并，再合并两组结果。划分依据是数组个数，不是某个数组内部的元素个数。即使各数组长度不同，每个元素也只会经历对数数量级的合并层。

函数与边界

定义 solve(lo, hi)：返回输入数组列表中下标区间 $[lo,hi)$ 内全部元素的有序新列表。

• 空区间返回 []。
• 区间只有一个数组时，返回该数组的副本，因为它已经有序。
• 否则取中点，将两组递归结果通过双指针合并。

合并两个有序列表时，比较两个指针所指的元素，取较小者并移动对应指针；一侧用完后追加另一侧剩余元素。相等时先取左侧，重复值均会保留。

正确性依据

单个数组的副本满足有序性和元素完整性。假设左右子调用都已正确返回各组元素，双指针每次取两个剩余序列中的最小首元素，因此输出始终非递减；每个输入元素恰好取出一次。合并结果正好包含当前区间的全部元素，归纳到根调用即可得到答案。

实现代码

Python 分治合并实现

def merge_sorted(left, right):
    """将两个非递减列表合并为一个新列表。"""
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result


def merge_k_sorted(arrays):
    """前提：每个输入数组已经非递减；不修改输入。"""
    def solve(lo, hi):
        if lo == hi:
            return []
        if hi - lo == 1:
            return arrays[lo].copy()
        mid = (lo + hi) // 2
        left = solve(lo, mid)
        right = solve(mid, hi)
        return merge_sorted(left, right)

    return solve(0, len(arrays))


for arrays in [
    [[1, 4, 7], [2, 5, 8], [0, 3, 6]],
    [[], [2, 2], [-1]],
    [],
    [[3]],
]:
    print(merge_k_sorted(arrays))

输出：

[0, 1, 2, 3, 4, 5, 6, 7, 8]
[-1, 2, 2]
[]
[3]

solve 通过下标划分数组列表；真正的元素比较集中在 merge_sorted。代码将各数组已有序作为输入前提，不额外排序，也不逐项验证有序性。

算法执行过程

对主示例，输入数组的编号为0、1、2；递归区间使用左闭右开表示。

调用或合并	子问题结果	当前结果
solve(0, 1)	第0个数组已经有序	[1, 4, 7]
solve(1, 2)	第1个数组已经有序	[2, 5, 8]
solve(2, 3)	第2个数组已经有序	[0, 3, 6]
solve(1, 3)	合并第1、2个数组	[0, 2, 3, 5, 6, 8]
solve(0, 3)	合并左右两组结果	[0, 1, 2, 3, 4, 5, 6, 7, 8]

最后一次合并先比较1与0，取0；再比较1与2，取1；随后交替比较两侧当前首元素，直到左侧的7被取出，再追加右侧的8。这里没有将3个数组补成4个，也没有丢弃空数组中的位置。

复杂度分析

按整数比较和列表元素读写为单位成本计数。

时间复杂度： $k\geq1$ 时为 $O(k+N\log(k+1))$。递归树含 $k$ 个叶子，需要 $O(k)$ 次调用工作；叶子复制共 $N$ 个元素；每个元素最多经过 $\lceil\log_2 k\rceil$ 次合并。这个上界适用于空数组和长度不同的数组。$k=0$ 时为 $O(1)$。

辅助空间复杂度： $O(N+\log(k+1))$，包括中间有序列表、合并时的切片和递归栈。顺序执行的递归不会使所有层的列表同时各占一份 $N$；当前存活的分组结果和合并结果总元素数为 $O(N)$。最终输出另需 $O(N)$ 空间；即使排除输出，中间列表仍可能占线性空间。

当 $k=1$ 时，代码仍复制唯一数组，因此时间与返回列表空间均为 $O(N+1)$，不能写成 $O(N\log k)=0$。

易错点

• 先拼接再排序。 能得到答案，但没有利用各数组已有序的条件，也不体现本题的分治合并过程。
• 相等时只保留一个值。 合并不是集合去重，两个相等元素都必须保留。
• 把单个输入数组直接作为可修改结果。 本实现返回副本，调用者修改结果不会改变输入数组。
• 忽略空数组带来的调用成本。 当 $N=0$、$k$ 很大时，仍需访问各叶子，时间为 $O(k)$。
• 把数组个数和元素总数混为一个规模。 深度由 $k$ 决定，各层搬运的元素数由 $N$ 决定。

课堂练习

1. 合并 [[1, 3], [], [2, 2], [-1, 5]]，写出结果。
2. 对4个各含3个元素的数组，分治树有几层合并？每层共处理多少个元素？
3. 输入包含100个空数组时，输出是什么？时间为何不是零？
4. 一个数组含1000个元素，另3个数组各含1个元素，是否仍可按数组个数对半划分？

参考答案

1. 结果为 [-1, 1, 2, 2, 3, 5]。
2. 两层合并。第一层两次合并各处理6个元素，第二层一次合并处理12个元素；每层合计12个元素。另有叶子复制的12次元素读写。
3. 输出 []。代码仍访问100个叶子及其内部父节点，时间为 $O(k)$。
4. 可以。划分仍保证调用深度为 $O(\log(k+1))$，每个元素经过的合并层数受这一深度限制；元素分布不均不会破坏正确性或上述上界。