如何实现时间复杂度为O(m*log m)的初始列表计算算法

这问题我熟！原来的实现慢就慢在list.index()上——每次找索引都要扫一遍列表，循环m次直接把复杂度拉到了O(m²)。要优化到O(m log m)，核心思路是用哈希字典提前存好元组到索引的映射，这样查索引就是O(1)的操作，再结合排序本身的O(m log m)，整体复杂度就达标了。

优化思路 #

• 先完成L1和L2的排序（这部分本身是O(m log m)，是复杂度的主要来源，无法再优化）
• 为排序后的L1、L2分别创建元组→索引的映射字典（O(m)时间）
• 利用字典快速查找索引，给每个元组添加第三个元素（O(m)时间）

具体代码实现 #

U = {(2,5), (5,1), (9,0), (6,4)}
m = len(U)

# Step 1: 完成排序，和原逻辑一致
L1 = sorted(U)  # 按元组第一个元素排序
L2 = sorted(U, key=lambda tup: tup[1])  # 按元组第二个元素排序

# Step 2: 建立元组到索引的映射字典（关键优化点）
l1_index_map = {tup: idx for idx, tup in enumerate(L1)}
l2_index_map = {tup: idx for idx, tup in enumerate(L2)}

# Step 3: 为L1添加L2中的索引
L1_with_index = [(t[0], t[1], l2_index_map[t]) for t in L1]
# 为L2添加L1中的索引
L2_with_index = [(t[0], t[1], l1_index_map[t]) for t in L2]

# 验证结果
print("L1:", L1_with_index)
# 输出: [(2, 5, 3), (5, 1, 1), (6, 4, 2), (9, 0, 0)]
print("L2:", L2_with_index)
# 输出: [(9, 0, 3), (5, 1, 1), (6, 4, 2), (2, 5, 0)]

复杂度分析 #

• 排序操作：sorted()的时间复杂度是O(m log m)，这是整个流程的主导复杂度
• 字典构建：遍历L1、L2各一次，时间复杂度O(m)
• 索引填充：遍历L1、L2各一次，每次字典查找是O(1)，时间复杂度O(m)
• 整体时间复杂度：O(m log m)，完全满足要求

额外说明 #

如果你的场景中U不是集合（允许存在重复元组），字典的键会冲突，这时可以调整映射逻辑：比如用「元组+原始索引」的组合作为键，但题目里U是集合，元组都是唯一的，这个方案完全适用。

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