列表数组去重是最常见的算法非常简单但不同实现方式背后的差异巨大。AI时代可以不手写代码了但需要知道代码背后的原理这样才能更好地指导AI编程。最简单的思路新建列表遍历原列表当原列表的元素不在新列表的则添加到新列表中。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)但会破坏原顺序函数式 / 递归写法上换一种风格适用不同场景本质仍是上面的方式相关源码见GitHub - microwind/algorithms: AI时代人人都是算法思想工程师。本项目含各种数据结构与经典算法充分举例说明用C/Java/Python/JS/Go/Rust等不同语言实现一边学算法一边学语言。助您打牢基础彻底理解编程的本质以便驾驭和用好AI。 · GitHub第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# 演示如何用递归构造结果工程上没有实用价值