Amazon VO：合并三个有序数组并去重，再扩展到 K 路

题意与假设

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

• 输入各数组非降序，空数组合法；训练元素为可比较整数。
• 保留每个不同值一次，不保留重复位置；输出排序。

解题路线

1. 三路可以三个指针比较最小当前值；K路用堆放每个非空流的首项，项包含(value,流号,下标)，避免同值无法区分推进哪个流。
2. 每次pop全局最小当前项，若不同于上次输出才追加，但无论是否重复都推进其来源流并将下一项入堆。忘记推进重复项会死循环或遗漏。
3. 所有未读元素都不小于所在流首项，堆最小首项就是全局未读最小；归纳输出排序。排序相同值相邻，因此只比较最后输出即可去重。
4. 迭代器/文件流版本只保留每路首项，不加载全部。若某流无排序保证，堆前沿证明失效，需要先排序或明确拒绝。

手动走一遍

训练[[1,1,4],[1,2,4],[],[2,3]]输出[1,2,3,4]；重复1仍要逐一消费，否则后续2和4无法出现。

Python 参考实现

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

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

from heapq import heappop,heappush


def merge_unique(arrays):
    heap=[]
    for i,arr in enumerate(arrays):
        if arr: heappush(heap,(arr[0],i,0))
    output=[]
    while heap:
        value,i,j=heappop(heap)
        if not output or value != output[-1]: output.append(value)
        j+=1
        if j < len(arrays[i]): heappush(heap,(arrays[i][j],i,j))
    return output

复杂度

总输入N，O(N log(k+1))时间、O(k)堆额外空间，O(u)输出；实际实现依非空流数量。

易错点与追问

容易失分的边界

• 重复项不推进。
• 把三个数组sort拼接后称流式。
• 输入未排序仍用堆前沿。

继续深挖

• 无限流怎样输出且避免某路阻塞？
• 每个值要统计跨流出现次数？
• 外部文件句柄限制下怎样多趟合并？