如何高效补全元组列表中的缺失日期？

现有若干元组列表，每个元组包含日期字符串和对应值：

list_1 = [('2023-01-01', 'a'), ('2023-01-02', 'b'), ('2023-01-10', 'c')]
list_2 = [('2023-01-02', 'd'), ('2023-01-05', 'e'), ('2023-01-07', 'f')]
list_3 = [('2023-01-01', 'g'), ('2023-01-03', 'h'), ('2023-01-10', 'i')]

需要为每个列表补全所有出现过的日期，缺失日期的对应位置填充None，预期结果如下：

list_1 = [('2023-01-01', 'a'),  ('2023-01-02', 'b'),  ('2023-01-03', None), ('2023-01-05', None), ('2023-01-07', None), ('2023-01-10', 'c')]
list_2 = [('2023-01-01', None), ('2023-01-02', 'd'),  ('2023-01-03', None), ('2023-01-05', 'e'), ('2023-01-07', 'f'), ('2023-01-10', None)]
list_3 = [('2023-01-01', 'g'),  ('2023-01-02', None), ('2023-01-03', 'h'),  ('2023-01-05', None), ('2023-01-07', None), ('2023-01-10', 'i')]

元组元素数量不固定，求最优高效的实现方案。

核心思路是利用字典快速查找和统一日期基准提升效率，步骤如下：

1. 收集并排序所有唯一日期
   提取所有列表中的日期，去重后按日期顺序排序（YYYY-MM-DD格式的字符串可直接按字典序排序），得到所有需要补全的日期集合。

2. 将每个列表转换为字典
   把每个元组列表转成{日期: 值}的字典，日期对应的取值操作时间复杂度为O(1)，大幅提升查找效率。

3. 生成补全后的列表
   遍历排序后的日期列表，对每个日期从对应字典中取值，不存在则用None，组成新的元组列表。

完整代码实现 #

# 原始列表
list_1 = [('2023-01-01', 'a'), ('2023-01-02', 'b'), ('2023-01-10', 'c')]
list_2 = [('2023-01-02', 'd'), ('2023-01-05', 'e'), ('2023-01-07', 'f')]
list_3 = [('2023-01-01', 'g'), ('2023-01-03', 'h'), ('2023-01-10', 'i')]

# 收集所有唯一日期并排序
all_dates = sorted({date for lst in [list_1, list_2, list_3] for date, _ in lst})

# 将每个列表转为字典
dict_1 = dict(list_1)
dict_2 = dict(list_2)
dict_3 = dict(list_3)

# 生成补全后的列表
list_1_completed = [(date, dict_1.get(date)) for date in all_dates]
list_2_completed = [(date, dict_2.get(date)) for date in all_dates]
list_3_completed = [(date, dict_3.get(date)) for date in all_dates]

# 输出结果
print("list_1 =", list_1_completed)
print("list_2 =", list_2_completed)
print("list_3 =", list_3_completed)

效率说明 #

• 时间复杂度：O(N + MK)，其中N是所有元组的总数，M是列表数量，K是唯一日期的数量。字典转换和日期收集都是线性时间，后续生成补全列表的操作也是线性遍历，整体效率远高于逐一遍历比对的O(NK)方案。
• 空间复杂度：O(N + K)，主要用于存储字典和日期集合，属于合理的空间开销。

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