本文介绍在不依赖排序的前提下，对包含数字的嵌套列表进行语义去重（即 [1,2] 与 [2,1] 视为重复）的最优解法，核心思路是用 frozenset 或 Counter 构建等价类哈希键，将时间复杂度从 O(mn log n) 降至 O(mn)。
本文介绍在不依赖排序的前提下，对包含数字的嵌套列表进行语义去重（即 `[1,2]` 与 `[2,1]` 视为重复）的最优解法，核心思路是用 `frozenset` 或 `counter` 构建等价类哈希键，将时间复杂度从 o(mn log n) 降至 o(mn)。
当处理形如 [[1, 2], [2, 1], [3, 4]] 的嵌套列表时，“唯一性”定义为元素集合相同即视为重复（忽略顺序与重复次数？需分情况讨论）。原始方案通过 sorted → tuple → set 实现，虽逻辑清晰，但排序引入了不必要的 O(n log n) 开销。实际上，只要能构造出稳定、可哈希、等价敏感的键（key），即可在单次遍历中完成去重，达到理论最优 O(mn) 时间复杂度（m 为子列表数量，n 为平均子列表长度）。
✅ 场景一：子列表内无重复元素（推荐 frozenset）
若每个子列表本身不含重复数字（如 [1, 2] 合法，[1, 1, 2] 不合法），则 frozenset(lst) 是最简、最高效的键：
def unique_unordered(lists):
seen = set()
result = []
for sub in lists:
key = frozenset(sub) # O(len(sub))，不可变且可哈希
if key not in seen:
seen.add(key)
result.append(sub) # 保留首次出现的原始形式
return result
# 示例
lists = [[1, 2], [2, 1], [3, 4], [4, 3], [1, 2, 5]]
print(unique_unordered(lists))
# 输出: [[1, 2], [3, 4], [1, 2, 5]]
该方案时间复杂度严格为 O(∑|sub|) = O(mn)，空间复杂度 O(mn)；且天然保留输入顺序与原始结构（如 [2,1] 不会变成 [1,2]）。
⚠️ 注意：
frozenset忽略顺序与重复，因此[1,1,2]和[1,2]会被视为等价——这在“无重复”前提下是正确行为；若需区分重复次数，则进入下一场景。
✅ 场景二：子列表内允许重复元素（使用 Counter）
当 [1,1,2] 和 [1,2] 需视为不同（即需保留多重性）时，frozenset 失效。此时应使用 collections.Counter 将子列表转化为「元素→频次」映射，并用 frozenset(Counter(...).items()) 构造键：
from collections import Counter
def unique_with_duplicates(lists):
seen = set()
result = []
for sub in lists:
# Counter(sub) 是 O(len(sub))；.items() 返回可哈希的元组序列
key = frozenset(Counter(sub).items())
if key not in seen:
seen.add(key)
result.append(sub)
return result
# 示例
lists = [[1, 1, 2], [2, 1, 1], [1, 2], [3, 3, 3]]
print(unique_with_duplicates(lists))
# 输出: [[1, 1, 2], [1, 2], [3, 3, 3]]
Counter(sub).items() 返回类似 [(1,2), (2,1)] 的无序视图，frozenset 消除顺序影响，确保等价性判断正确。
? 简洁写法（牺牲顺序保留，适合结果无关原始形态的场景）
若仅需任意一个代表（不要求保留首次出现的原始列表），可用一行式表达：
# 无重复元素时（返回 list of list，顺序不定）
def unique_simple(lists):
return [list(s) for s in set(frozenset(lst) for lst in lists)]
# 有重复元素时
from collections import Counter
def unique_simple_counter(lists):
return [list(lst) for lst in {frozenset(Counter(lst).items()): lst for lst in lists}.values()]
? 性能与选型建议
- 小规模数据（n ：原始
sorted + tuple方案因常数小、C 语言优化充分，实际可能更快； -
大规模或高频调用：
frozenset/Counter方案理论与实测均更优； -
内存敏感场景：避免生成中间
tuple列表，采用生成器+set迭代式去重（如上所示）； -
稳定性要求：若必须保留原始子列表形态（如
[2,1]而非[1,2]），务必使用带result.append(sub)的显式循环，而非map(list, set(...))。
综上，通过合理选择哈希键类型（frozenset vs Counter.items()），可在 O(mn) 时间内完成语义去重，兼顾效率、可读性与边界鲁棒性。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
