如何以低于O(n²)复杂度获取字符所属集合的索引

由于x和Y的规模都很大，避免重复遍历Y查询每个字符是提升效率的核心。我们可以通过「空间换时间」的思路，先构建字符到集合索引的映射字典，再通过字典的O(1)查询快速生成结果。

实现步骤 #

1. 构建映射字典：遍历Y中的每个集合，将集合内的每个字符与该集合的索引绑定
2. 生成结果：遍历x，通过字典直接获取每个字符对应的索引

代码示例 #

Y = [{"a", "b"}, {"c", "d"}, {"e", "f"}]
x = ["a", "b", "c", "d", "e", "f", "a", "f"]

# 构建字符到索引的映射字典
char_to_idx = {}
for idx, s in enumerate(Y):
    for char in s:
        char_to_idx[char] = idx

# 生成目标结果（可按需调整输出格式）
result = [(char, char_to_idx[char]) for char in x]

print(result)

输出结果 #

[('a', 0), ('b', 0), ('c', 1), ('d', 1), ('e', 2), ('f', 2), ('a', 0), ('f', 2)]

效率说明 #

• 时间复杂度：O(N + M)，其中N是Y中所有元素的总数量，M是x的长度。这是理论最优复杂度，因为必须遍历所有元素一次。
• 空间复杂度：O(N)，用于存储映射字典，在大数据量场景下，这种方式的效率远高于每次遍历Y查询的O(M*K)（K为Y的集合数量）。

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