给定两个有序列表，按总和的顺序迭代对

Question

我有两个有序列表 list1 和 list2。我想迭代 (x, y) 对，其中 x 在 list1 中，y 在 list2 中，按照对总和的顺序。我不关心以什么顺序输出具有相同总和的对。

例如给定 [1, 2, 3], [2, 4, 6]，我应该输出：

(1, 2), (2, 2), (1, 4), (3, 2), (2, 4), (1, 6), (3, 4), (2, 6), ( 3, 6)

总和为：3, 4, 5, 5, 6, 7, 7, 8, 9

我对以某种方式合并列表然后对其进行排序的方法不感兴趣。例如，一般来说，在输出具有第 20 个最小总和的对之前，我不想做一些取决于列表大小的工作。

满足这些要求的一种算法是什么？

Answer 1

您可以使用 minheap 数据结构。

堆中的条目将是一个具有总和的元组，以及促成该总和的两个索引。

辅助数据结构必须确保堆中没有重复的条目，即具有相同索引对的两个条目。一个简单的哈希集就可以做到这一点。

从基于索引 (0, 0) 的堆上的一个条目开始。

然后在堆中有条目时进行循环，每次从堆中提取最小元素（具有最小总和），输出它，然后向堆中添加两个条目，每个条目都会增加两个索引之一。如果此类条目已在堆中，请忽略它，或者如果下一个索引超出范围，请忽略它。

这是 Python 中的实现（具有本机堆支持）：

from heapq import heappush, heappop

def mergebysum(a, b):
    heap = [(a[0] + b[0], 0, 0)]
    inheap = set([(0, 0)])
    while heap:
        _, i, j = heappop(heap)
        inheap.remove((i, j))
        yield a[i], b[j]
        if i + 1 < len(a) and (i + 1, j) not in inheap:
            heappush(heap, (a[i+1]+b[j], i+1, j))
            inheap.add((i+1, j))
        if j + 1 < len(b) and (i, j + 1) not in inheap:
            heappush(heap, (a[i]+b[j+1], i, j+1))
            inheap.add((i, j+1))

这是一个运行示例：

a = [1, 2, 3]
b = [2, 4, 6]
for x, y in mergebysum(a, b):
    print((x, y))

输出如您在问题中列出的那样。

该解决方案的空间复杂度为 O(𝑛+𝑚)，其中 𝑛 和 𝑚 是两个输入列表的大小。时间复杂度由输出大小和堆开销决定，即 O(𝑛𝑚log(𝑛+𝑚))。