Meta 三组有序数组去重归并：指针同步推进

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 三个数组均非降排序，可为空，元素可为负。结果包含每个值一次，输入不修改。
• 部分题目只写merge未声明dedup；此实现采用明确的去重变体，若需保留重复必须改变推进与输出。

解题路线

1. 每次从三组当前头部取最小值，向输出追加一次，再将所有等于该值的头部连续跳过。
2. 任何尚未处理的元素都不小于各自头，故当前最小头是全体剩余最小；同步跳重复不可能漏掉其他值。
3. 数组数固定3，每步最多比较三头，所有指针只前进，总代价线性。推广k路流时用堆避免每次扫描k个头。

手动走一遍

[1,1,4]、[1,2,4]、[2,3]输出[1,2,3,4]；值1先输出一次，再跳过前两组所有1。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def merge_three_sorted(first, second, third):
    rows = (first, second, third)
    if any(any(a[i] > a[i + 1] for i in range(len(a) - 1)) for a in rows):
        raise ValueError("inputs must be sorted")
    positions = [0, 0, 0]
    result = []
    while True:
        active = [j for j in range(3) if positions[j] < len(rows[j])]
        if not active:
            return result
        smallest = min(rows[j][positions[j]] for j in active)
        if not result or result[-1] != smallest:
            result.append(smallest)
        for j in active:
            while positions[j] < len(rows[j]) and rows[j][positions[j]] == smallest:
                positions[j] += 1

复杂度

O(N)时间，O(1)辅助指针（3固定），O(U)结果空间；k路推广堆O(N log k)、O(k)堆空间。

易错点与追问

容易失分的边界

• 只推进被选中的一个数组会重复输出或多做比较；可保留输出最后值检查，但同步跳过更直接。
• 集合再排序可得到答案，却需要O(U log U)排序并浪费输入已排序条件。

继续深挖

• 无法随机访问的流要保留每路当前头和耗尽标记，重复值推进逐个next。
• 若值是带payload对象，以哪个key去重、重复payload保留哪个版本，需要明确合同。