如何高效从Python列表的列表中提取所有重复子列表元素

现有存储整数对的嵌套列表，示例如下：

example_list = [[0, 0], [0, 1], [0, 1], [5, 4]]

需求为用高性能方式，提取原列表中所有出现次数至少为2次的元素组成新列表。以上述示例为例，期望输出结果为：

new_list = [[0, 1]]

其中[0,1]是唯一满足重复次数要求的条目。

• 列表推导+count()写法：可以得到正确结果，但时间复杂度为O(n²)，每次调用count()都会全量遍历整个列表，数据规模稍大时运行速度无法满足要求。
• 自定义字典累加写法：逻辑和需求完全不匹配，该代码实际是按子列表第一个元素分组、累加第二个元素的数值，并非统计整个子列表的出现频次，运行后输出{0: 2, 5: 4}，和预期结果完全不符。
• 改写的Counter实现：生成器逻辑错误，代码实际是将子列表第二个值作为重复次数，展开第一个值做单值计数，本质没有统计整个子列表的出现频次，运行后输出Counter({5: 4, 0: 2})，不符合需求。

列表属于不可哈希类型，无法直接作为字典/计数器的键，只要先将子列表转换为可哈希的元组做频次统计，就能实现O(n)时间复杂度的高效查重，性能远高于count()写法。

基于collections.Counter的实现 #

代码简洁，执行效率高：

from collections import Counter

example_list = [[0, 0], [0, 1], [0, 1], [5, 4]]
# 转元组统计频次，过滤后转回列表格式
item_counts = Counter(tuple(sub_list) for sub_list in example_list)
new_list = [list(key) for key, cnt in item_counts.items() if cnt >= 2]

运行后new_list的值为[[0, 1]]，完全符合预期。

不依赖额外模块的原生字典实现 #

如果不想导入标准库额外类，用原生字典即可实现同等性能的逻辑：

example_list = [[0, 0], [0, 1], [0, 1], [5, 4]]
item_counts = {}
for sub_list in example_list:
    key = tuple(sub_list)
    item_counts[key] = item_counts.get(key, 0) + 1
new_list = [list(key) for key, cnt in item_counts.items() if cnt >= 2]

两种方案都仅需遍历原列表2次（1次统计频次、1次过滤结果），即使处理十万级以上规模的嵌套列表，也能保持极快的运行速度。

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