如何用时间复杂度为O(n)的单行代码反转含非唯一值的字典？能否写出时间复杂度优于O(n²)的字典推导式单行代码？

当然可以实现时间复杂度优于O(n²)的单行代码，甚至是**严格O(n)**的方案！先直接上可行的单行实现，再给你拆解背后的逻辑：

直接解决方案（O(n)单行） #

如果你想用普通字典（不需要导入额外模块），可以这样写：

my_map = {'A': 'x', 'B': 'y', 'C': 'x', 'D': 'z'}
rev_map = {}; _ = [rev_map.setdefault(b, []).append(a) for a, b in my_map.items()]

如果可以导入collections模块，用defaultdict会更直观一点：

from collections import defaultdict
my_map = {'A': 'x', 'B': 'y', 'C': 'x', 'D': 'z'}
rev_map = defaultdict(list); _ = [rev_map[b].append(a) for a, b in my_map.items()]

为什么原来的代码是O(n²)？ #

你原来的推导式：

rev_map = {b: [a2 for a2 in my_map.keys() if my_map[a2] == b] for a, b in my_map.items()}

问题出在嵌套遍历：外层遍历每个键值对时，内层又要完整遍历一次整个字典的键，去筛选出对应的值。比如原字典里有两个键对应'x'，那这个值会触发两次全字典遍历，整体时间复杂度直接升到O(n²)，而且还存在大量重复计算。

为什么新方案是O(n)？ #

这个单行逻辑的核心是只遍历原字典一次：

1. 我们初始化一个空字典（或defaultdict(list)）用来存反转后的映射
2. 用列表推导式遍历原字典的每个键值对(a, b)：
   • rev_map.setdefault(b, [])会检查键b是否存在，不存在就创建一个空列表作为值
   • 然后直接把当前键aappend到对应的列表里
3. 整个过程中每个键值对只被处理一次，setdefault和列表append都是均摊O(1)的操作，所以整体时间复杂度是严格的O(n)

注：这里用_接收列表推导式的返回值，是因为推导式执行后会生成一个全是None的列表（append方法返回None），我们不需要这个列表，用下划线表示“忽略这个变量”是Python里的惯例。

有没有更“优雅”的单行？ #

如果你觉得用列表推导式做副作用有点别扭，也可以用functools.reduce写单行（但可读性稍差）：

from functools import reduce
rev_map = reduce(lambda d, kv: d.setdefault(kv[1], []).append(kv[0]) or d, my_map.items(), {})

这里利用or运算符的特性：append返回None，所以会返回后面的d，最终reduce会返回构建好的字典。不过相比之前的方案，这个可读性没那么高，日常开发里还是推荐前两种。

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