本文介绍在 Python 中对列表嵌套结构进行语义去重的多种方法，核心是将 [1,2] 与 [2,1] 视为等价，通过 frozenset 或 Counter 构建哈希友好的唯一键，实现线性时间复杂度 O(mn) 的去重算法。
本文介绍在 python 中对列表嵌套结构进行语义去重的多种方法，核心是将 `[1,2]` 与 `[2,1]` 视为等价，通过 frozenset 或 counter 构建哈希友好的唯一键，实现线性时间复杂度 o(mn) 的去重算法。
在处理嵌套列表（如 [[1, 2], [2, 1], [3, 4]]）时，若需按元素集合等价性而非顺序一致性去重（即 [1,2] ≡ [2,1]），传统排序 + tuple 转换方案虽直观，但时间复杂度为 O(mn log n)（m 为外层数量，n 为平均子列表长度）。实际上，我们可通过更本质的抽象——多重集（multiset）表示——将其优化至理论最优的 O(mn)。
✅ 场景一：子列表元素互异（无重复）
当每个子列表内部不含重复元素时，frozenset 是最简洁高效的键构造方式。它忽略顺序、天然可哈希，且构建时间为 O(n)：
def unique_no_duplicates(lists):
seen = set()
result = []
for sub in lists:
key = frozenset(sub)
if key not in seen:
result.append(sub)
seen.add(key)
return result
# 示例
lists = [[1, 2], [2, 1], [3, 4], [4, 3], [1, 2, 3]]
print(unique_no_duplicates(lists))
# 输出: [[1, 2], [3, 4], [1, 2, 3]]
该版本保留原始输入中首次出现的代表列表（如 [1, 2] 而非 [2, 1]），语义清晰、内存友好。若仅需任意一个合法代表（不关心原始顺序），可进一步简化为单行式：
from typing import List
def unique_any_order(lists: List[List[int]]) -> List[List[int]]:
return [list(s) for s in set(frozenset(sub) for sub in lists)]
✅ 场景二：子列表允许重复元素（如 [1,1,2] 与 [1,2,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).items() 返回类似 [(1,2), (2,1)]，frozenset 使其可哈希
key = frozenset(Counter(sub).items())
if key not in seen:
result.append(sub)
seen.add(key)
return result
# 示例
lists = [[1, 1, 2], [2, 1, 1], [1, 2, 2], [3, 3]]
print(unique_with_duplicates(lists))
# 输出: [[1, 1, 2], [1, 2, 2], [3, 3]]
⚠️ 注意：Counter(sub).items() 的顺序不保证一致，但 frozenset 能正确处理无序键值对集合，确保等价性判断可靠。
? 性能与选型建议
-
理论优势：
frozenset/Counter方案将主导项从排序的O(n log n)降为O(n)，总复杂度降至 O(mn)。 -
实际权衡：当
n较小（如 ≤ 10）时，Python 内置sorted()高度优化，可能比构造Counter或frozenset更快；建议在真实数据上 benchmark 验证。 - 空间开销：所有方案均需额外 O(mn) 空间存储中间键或结果，无法避免。
-
稳定性：前两种显式循环版本保持输入顺序；
set(map(...))版本不保证顺序（Python 3.7+ dict 有序，但 set 仍无序）。
综上，选择策略应基于数据特征：无重复 → frozenset；有重复 → Counter；追求极致简洁且接受任意顺序 → 单行函数；追求稳定顺序与可控逻辑 → 显式遍历 + seen 集合。
