带缺失key前向继承机制的有序列表高效合并算法咨询

需求说明 #

我正在处理多个按key升序排列的列表，每个列表包含(key, value)形式的元组。需要将这些列表合并为一个包含所有输入列表中唯一key的有序列表，输出元组格式为：

(key, value_from_list1, value_from_list2, ..., value_from_listK)

需遵循以下规则：

• 每个唯一key对应一个输出元组，包含各列表的「当前值」
• 若某列表无该key的条目，沿用该列表小于等于当前key的最新有效值（初始默认值为null）
• 所有输入列表默认包含(0, null)，但最终输出需省略这个初始元组

示例1 #

输入：

A = [(1, a1), (2, a2), (10, a3)]
B = [(1, b1), (8, b2), (10, b3)]

期望输出：

C = [
  (1, a1, b1),  # key=1时，两个列表都提供了值
  (2, a2, b1),  # key=2时，A更新为a2，B仍用b1
  (8, a2, b2),  # key=8时，B更新为b2，A保持a2
  (10, a3, b3)  # key=10时，两个列表都更新
]

示例2 #

输入：

A = [(1, a1)]
B = [(2, b1)]

期望输出：

[(1, a1, null), (2, a1, b1)]

核心问题 #

1. 算法效率：带缺失Key前向继承机制的有序列表合并，最有效的算法是什么？

当前采用多指针扫线算法，跟踪各列表最近值，遍历所有唯一key，时间复杂度为O(N logN)。

2025-03-13 更新：优化后的伪代码 #

有观点指出：

若需为每个key输出k个值，最有效的算法时间复杂度为Θ(k·u)，其中u是唯一key的数量。

基于此编写的伪代码如下：

函数 mergeLists(lists):
    k = 列表数量
    pointers = 长度为k的数组，初始全为0
    lastValues = 长度为k的数组，初始设为None（或默认值）
    output = 空列表

    循环：
        minKey = None

        // 找出所有列表当前指针位置中最小的key
        遍历i从0到k-1：
            若 pointers[i] < 列表lists[i]的长度：
                currentKey = lists[i][pointers[i]].key
                若 minKey 为None 或 currentKey < minKey：
                    minKey = currentKey

        // 若找不到minKey，说明所有列表已遍历完毕
        若 minKey 为None：
            跳出循环

        // 更新所有包含当前minKey的列表的lastValues
        遍历i从0到k-1：
            若 pointers[i] < 列表lists[i]的长度 且 lists[i][pointers[i]].key == minKey：
                lastValues[i] = lists[i][pointers[i]].value
                pointers[i] = pointers[i] + 1

        // 将合并后的元组加入输出列表
        output.append( (minKey, lastValues[0], lastValues[1], ..., lastValues[k-1]) )

    返回 output

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