【Python列表去重的20种方法，总有一种你不知道】

最简单的思路新建列表遍历原列表当原列表的元素不在新列表的则添加到新列表中。def unique(data):# 新建listnew_list []for item in data:# 原list中的项是否存在于新list中不存在则添加。这是 O(n)操作if item not in new_list:new_list.append(item)return new_list这种写法最直观易懂但每次not in都要遍历整个new_list复杂度为 O(n²)。如何降低复杂度呢可以从以下角度思考哈希集合 / 字典把查询从 O(n) 可压到 O(1)整体 O(n)先排序相同元素两两比较再去重O(nlogn)但会破坏原顺序函数式 / 递归写法上换一种风格适用不同场景本质仍是上面的方式相关源码见https://github.com/microwind/algorithms第1类基础循环方法1-8策略原理遍历原数组直接用双重循环或下标比较找出重复项。每一步判断是否存在都是 O(n)整体复杂度 O(n²)。适用场景这里主要是展示算法原理用于教学示例弄懂编程原理。生产代码不建议使用。否是原列表取下一个元素遍历结果列表是否已存在?追加到结果跳过继续# 方法1最基础的线性查找def unique_v1(data):new_list []for item in data:# in 在列表上是 O(n) 扫描整体 O(n²)# 该元素不在新list则添加if item not in new_list:new_list.append(item)return new_list# 方法2用下标遍历def unique_v2(data):new_list []for i in range(len(data)):# 与第1种相同遍历方式换成range复杂度不变if data[i] not in new_list:new_list.append(data[i])return new_list# 方法3列表推导式def unique_v3(data):new_list []# 利用列表推导式的副作用追加元素写法简化本质与前面一样[new_list.append(i) for i in data if i not in new_list]return new_list# 方法4通过元素首次出现位置判断def unique_v4(data):new_list []for i in range(len(data)):# data.index(x) 返回 x 在 data 里第一次出现的下标# 当前下标恰好等于该值时说明该元素是首次出现将首次出现的添加到新listif i data.index(data[i]):new_list.append(data[i])return new_list# 方法5原地删除从右往左扫描def unique_v5(data):l len(data)while l 0:l - 1i lwhile i 0:i - 1# 在 [0, l) 区间里寻找与 data[l] 相同的元素# 找到就删后面那个保留前面的if data[i] data[l]:del data[l]breakreturn data# 修改原列表空间 O(1)# 方法6原地删除从左往右扫def unique_v6(data):l len(data)i 0while i l:j i 1while j l:# 把 data[i] 后面所有等于它的元素删掉if data[i] data[j]:del data[j]l - 1 # 列表变短长度同步更新else:j 1i 1return data# 方法7用 try-except 替代 indef unique_v7(data):new_list []for item in data:try:# index 找不到会抛 ValueErrornew_list.index(item)except ValueError:# 找不到才追加new_list.append(item)return new_list# 实际上不会这么使用——拿异常处理正常的控制流性能和可读性都吃亏# 方法8双层循环下标判断def unique_v8(data):new_list []for i in range(len(data)):j 0while j i:# 看 data[i] 在它之前是否出现过if data[i] data[j]:# 只有 j i前面都没遇到时才追加if i j:new_list.append(data[i])breakj 1return new_list# 内层只跑到 i 而非 n比较次数约为方法1的一半但渐进复杂度仍是 O(n²)第2类哈希表方法9-12策略原理利用dict或set的键Key唯一性来记录已经出现的元素。哈希结构的查询是 O(1)因此整体降到 O(n)。代价是需要 O(n) 额外内存空间且元素必须可哈希——数字、字符串、元组都可以但 list、dict 这类可变对象不行。适用场景日常项目的首选。需要保留原顺序时尤其合适因为一边查重一边按原序写入结果。否是原列表取下一个元素已在 seen 列表中?seen.add追加结果跳过继续# 方法9set 配合 list——工程最常见写法def unique_v9(data):seen set() # set 用于 O(1) 判重result [] # list 用于保持原顺序for item in data:if item not in seen:seen.add(item)result.append(item)return result# 方法10dict.fromkeys()——最佳版本实际使用首选def unique_v10(data):# dict 自 Python 3.7 起保持插入顺序# fromkeys 会自动用相同 key 覆盖从而完成去重return list(dict.fromkeys(data))# 方法11filter 列表函数式风格def unique_v11(data):seen []# 内部函数def check(item):# 闭包捕获 seen# 注意 seen 是 listin 仍是 O(n)整体仍是 O(n²)if item not in seen:seen.append(item)return Truereturn Falsereturn list(filter(check, data))# 函数式风格但不纯粹seen 类型选错了这里只是为了展示写法# 方法12filter 字典由list改为dict仍然不是纯函数式def unique_v12(data):obj {}def check(item):# 用 dict 替代上面的 list查询变成 O(1)if obj.get(item) is None:obj[item] itemreturn Truereturn Falsereturn list(filter(check, data))第3类集合与排序方法13-16策略原理将list直接转set或者通过sort()让相同元素挨在一起再去重从而简化查找逻辑。两种思路都不再保留原有顺序。集合方式 O(n)排序方式 O(nlogn)且要求元素可比较。适用场景不关心顺序、只关心结果集合的场合例如统计去重数量、做集合运算、把列表当作无序集合使用。哈希有序是否原列表选择策略转 set天然去重排序相同元素相邻相邻是否相同?删后者保留结果# 方法13set 直接转列表常见用法def unique_v13(data):# 哈希集合天然不重复return list(set(data))# 写法最短但顺序会被打乱# 方法14map filter 组合def unique_v14(data):seen []def mark(item):# 第一次见到返回元素本身后续返回 Noneif item not in seen:seen.append(item)return itemreturn None# 先 map 标记再 filter 把 None 去掉return list(filter(lambda x: x is not None, map(mark, data)))# 函数式风格但 seen 用 list 仍是 O(n²)# 方法15先排序再相邻去重从右往左删def unique_v15(data):data.sort() # 排序后相同元素会聚到一起l len(data)while l 0:l - 1# 相邻两两比较相同就删后面那个if l 0 and data[l] data[l-1]:del data[l]return data# 复杂度由 sort 决定O(nlogn)元素需要可比较# 方法16先排序再相邻去重从左往右删def unique_v16(data):data.sort()l len(data) - 1i 0while i l:if data[i] data[i1]:del data[i] # 删当前i 不前进同时长度减一i - 1l - 1i 1return data第4类函数式与递归方法17-20策略原理用reduce、外部库或递归换一种表达方式。reduce配合元组累加器可以做到 O(n)但写法比直接 for 循环晦涩递归则吃调用栈、numpy 需要库依赖。适用场景numpy 适合大规模数值数据其余几种主要用于练习函数式或递归思维工程上一般直接用第 2 类。是否是否列表 lengthnlength 1?返回检查末尾元素是否在前面出现重复?丢弃末尾保留末尾递归处理 length-1# 方法17reduce 元组累加器函数式风格但能跑到 O(n)import functoolsdef unique_v17(data):def foo(acc, item):# 累加器是一个元组 (result, seen)# result 保留首次出现的顺序seen 用集合实现 O(1) 判重result, seen accif item in seen:return (result, seen)# 这里直接修改累加器内部的 list 和 set# 严格的纯函数式应返回新对象 (result [item], seen | {item})# 但那样每步都新建列表/集合复杂度退回到 O(n²)# 在 reduce 内做受控副作用换取 O(n) 的性能seen.add(item)result.append(item)return (result, seen)# 初始累加器是空列表空集合最后取 [0] 即得到去重结果return functools.reduce(foo, data, ([], set()))[0]# O(n)保序本质是用 reduce 重写了方法9的循环# 方法18调用 numpy.uniquedef unique_v18(data):import numpy as np# numpy 底层用 C 实现的排序相邻去重return list(np.unique(np.array(data)))# O(nlogn)不保序适合大规模数值数据# 方法19递归原地删除def unique_v19(data, lengthNone):# 递归退出条件if length is None:length len(data)if length 1:return datalast_idx length - 1# 看末尾元素是否在前面出现过is_repeat Falsefor i in range(last_idx):if data[i] data[last_idx]:is_repeat Truebreak# 重复则删除if is_repeat:del data[last_idx]# 递归调用处理前 length-1 项return unique_v19(data, length - 1)# 递归深度 n大数据会栈溢出仅作学习用# 方法20递归拼接返回不修改原列表# 递归自后往前逐个调用当长度为1时终止。与上一个递归不同这里将不重复的项目作为结果拼接起来def unique_v20(data, lengthNone):if length is None:length len(data)if length 1:return datalast_idx length - 1last_item data[last_idx]is_repeat Falsefor i in range(last_idx):if data[i] last_item:is_repeat Truebreak# 末尾元素重复就丢弃否则拼到结果末尾result [] if is_repeat else [last_item]# 切片 拼接都会产生新列表空间开销大return unique_v20(data[:last_idx], length - 1) result# 演示如何用递归构造结果工程上没有实用价值这么多实现方式如何选择不需要需要十万级以上一般规模代码简洁逻辑清晰学习练手列表去重是否需要保持顺序优先看性能保留原顺序数据规模numpy.unique()排序实现性能稳list(set(data))最快、最短侧重点dict.fromkeys()推荐方案set list 组合工程常见递归 / reduce编程研究用类别时间复杂度是否保序主要场景基础循环O(n²)是教学、极小规模哈希表O(n)是日常项目首选集合 / 排序O(n) / O(nlogn)否不在意顺序函数式 / 递归视实现而定看实现学习、特定场景实际项目里怎么选绝大多数情况一行就够# 保序、O(n)、对所有可哈希类型有效Python 3.7 自带result list(dict.fromkeys(data))不在意顺序result list(set(data))数据量很大且都是数值import numpy as npresult list(np.unique(data))带逻辑干预的去重前面所有方法都把重复的元素直接丢掉。但实际工作里经常遇到这样的情况遇到重复时不能简单丢弃要根据某个条件做处理。比如按id去重但要保留分数最高的那条记录去重的同时累加重复次数即频次统计数值在某个区间内才参与去重区间外原样保留这类需求set和dict.fromkeys都没法直接表达需要把判重和处理两步拆开来写。def unique_with_rule(data, keyNone, on_duplicateNone):带逻辑干预的去重。key: 可哈希的去重键默认拿元素本身on_duplicate: 遇到重复时如何处理 (旧值, 新值) - 新的代表值返回 None 时保持旧值不变即等同于丢弃新值if key is None:key lambda x: xchosen {} # 键 - 当前选中的元素order [] # 记录键首次出现的顺序保证保序for item in data:k key(item)if k not in chosen:chosen[k] itemorder.append(k)elif on_duplicate is not None:# 遇到重复时由调用方决定如何合并merged on_duplicate(chosen[k], item)if merged is not None:chosen[k] mergedreturn [chosen[k] for k in order]例 1按id去重保留分数最高的students [{id: 1, name: 张三, score: 90},{id: 1, name: 张三, score: 95}, # 同 id分数更高{id: 2, name: 李四, score: 99},]result unique_with_rule(students,keylambda x: x[id],on_duplicatelambda old, new: new if new[score] old[score] else old,)# [{id:1,score:95,...}, {id:2,score:99,...}]例 2去重的同时统计每个值的出现次数from collections import Counterdata [A, B, A, C, B, A]# Counter 本身就是键-计数遍历一次即可完成统计counts Counter(data)# Python 3.7 起 dict / Counter 保留插入顺序因此 keys 即首次出现顺序unique_keys list(counts.keys())# unique_keys [A, B, C]# counts {A: 3, B: 2, C: 1}例 3区间过滤——只对[0, 50]区间内的值去重区间外的原样保留data [5, 12, 5, 100, 12, 200]seen set()result []for x in data:if 0 x 50:# 区间内才参与去重if x in seen:continueseen.add(x)# 区间外或首次出现都保留result.append(x)# [5, 12, 100, 200]这三个例子是同一种思路把判重与业务规则分开。判重用哈希结构保证 O(n)规则部分留给回调或显式分支处理这样既不丢性能又能容纳各种业务变化。处理不可哈希的元素如果列表里是 dict、list 这类不可哈希对象前面的set/dict.fromkeys都用不了需要自己提供去重键def deduplicate_with_key(data, keyNone):按自定义 key 去重保留首次出现的元素if key is None:return list(dict.fromkeys(data))seen set()result []for item in data:# 把不可哈希的整体映射成可哈希的键k key(item)if k not in seen:seen.add(k)result.append(item)return result# 使用示例按学生 id 去重students [{id: 1, name: 张三, score: 90},{id: 1, name: 张三, score: 95}, # id 重复{id: 2, name: 李四, score: 85},]result deduplicate_with_key(students, keylambda x: x[id])# 只保留第一个 id1 的学生利用set.add()返回 None 的小技巧也能把保序去重压成一行但可读性下降实际代码不建议def deduplicate_short(data):seen set()# x in seen 为 False 时才会执行 seen.add(x)# add 返回 None 让 or 短路整个表达式得到 False于是元素被保留return [x for x in data if not (x in seen or seen.add(x))]总结默认就用list(dict.fromkeys(data))保序、复杂度 O(n)、一行搞定不需要保序就用list(set(data))利用数据结构特性大规模数值数据用numpy.unique借助外部库