求按元素对和升序遍历两个有序列表的高效算法

核心思路 #

因为两个列表都是升序排列的，最小的元素对和必然是两个列表第一个元素的和。后续的次小和，只能来自当前最小元素对的「右侧相邻元素对」或者「下侧相邻元素对」（也就是索引(i+1,j)或(i,j+1)）。我们可以用**最小堆（优先队列）**来维护这些候选元素对，同时用一个集合记录已经处理过的索引对，避免重复加入堆中。

具体步骤 #

• 初始化最小堆，将第一个元素对的和、对应索引对 (0,0) 放入堆中。
• 用一个集合 visited 标记已加入堆的索引对，初始时把 (0,0) 加入。
• 循环执行以下操作直到堆为空：
  1. 弹出堆顶元素（当前和最小的元素对），输出对应的 (list1[i], list2[j])。
  2. 如果 i+1 没有超出 list1 的长度，且 (i+1, j) 不在 visited 中，就把 (list1[i+1]+list2[j], i+1, j) 加入堆，并将 (i+1,j) 标记为已访问。
  3. 如果 j+1 没有超出 list2 的长度，且 (i, j+1) 不在 visited 中，就把 (list1[i]+list2[j+1], i, j+1) 加入堆，并将 (i,j+1) 标记为已访问。

代码示例（Python） #

import heapq

def traverse_pairs(list1, list2):
    if not list1 or not list2:
        return
    
    m, n = len(list1), len(list2)
    heap = []
    visited = set()
    
    # 初始化堆
    initial_sum = list1[0] + list2[0]
    heapq.heappush(heap, (initial_sum, 0, 0))
    visited.add((0, 0))
    
    while heap:
        current_sum, i, j = heapq.heappop(heap)
        print(f"({list1[i]}, {list2[j]})", end=", ")
        
        # 处理下一个i的元素对
        if i + 1 < m and (i+1, j) not in visited:
            next_sum = list1[i+1] + list2[j]
            heapq.heappush(heap, (next_sum, i+1, j))
            visited.add((i+1, j))
        
        # 处理下一个j的元素对
        if j + 1 < n and (i, j+1) not in visited:
            next_sum = list1[i] + list2[j+1]
            heapq.heappush(heap, (next_sum, i, j+1))
            visited.add((i, j+1))

# 测试示例
list1 = [1,2,3]
list2 = [2,4,6]
traverse_pairs(list1, list2)
# 输出：(1, 2), (2, 2), (1, 4), (3, 2), (2, 4), (1, 6), (3, 4), (2, 6), (3, 6), 

为什么这个方法符合要求 #

• 不需要提前生成所有元素对，每次只处理当前最小的候选，内存占用远小于全量生成的方案。
• 当只需要获取前k个最小和的元素对时，时间复杂度为O(k log k)，效率很高，不会做多余的预处理工作。
• 天然保证了元素对按和升序输出，和相同的元素对顺序由堆的弹出顺序决定，符合题目要求。

内容的提问来源于stack exchange，提问作者j x