Python 算法基础篇之集合

1. 集合是什么？

1.1 生活中的集合

想象你有一个音乐播放列表，里面收藏了你喜欢的歌曲。这个播放列表有几个特点：

• 没有重复：同一首歌不会收藏两次
• 无序排列：你不在乎哪首歌在前哪首在后
• 快速查找：你能瞬间判断某首歌是否在列表中

这就是集合的本质！

集合（Set）：一种无序、不重复的元素集合，基于哈希表实现，支持 O(1) 的成员检测。

1.2 为什么需要集合？

# 场景：从用户行为日志中提取去重后的用户IDuser_logs=[1001,1002,1001,1003,1002,1004,1001]# 用列表去重（低效）unique_users_list=[]foruidinuser_logs:ifuidnotinunique_users_list:# O(n) 查找！unique_users_list.append(uid)print(unique_users_list)# [1001, 1002, 1003, 1004]# 时间复杂度：O(n²)# 用集合去重（高效）unique_users_set=set(user_logs)# O(n)print(unique_users_set)# {1001, 1002, 1003, 1004}# 时间复杂度：O(n)

💡核心优势：集合的in操作是O(1)，列表是O(n)。数据量越大，差距越明显。

2. 集合的创建与基本操作

2.1 创建集合的四种方式

# 方式1：花括号（注意：空{}是字典！）s1={1,2,3,4,5}print(type(s1))# <class 'set'># 方式2：set() 构造函数s2=set([3,4,5,6,7])# 从列表s3=set((1,2,3))# 从元组s4=set("hello")# 从字符串 → {'h', 'e', 'l', 'o'}s5=set(range(5))# 从 range → {0, 1, 2, 3, 4}# 方式3：集合推导式（类似列表推导式）s6={x**2forxinrange(10)ifx%2==0}# {0, 4, 16, 36, 64}# 方式4：frozenset（不可变集合，可作为字典键）fs=frozenset([1,2,3])print(type(fs))# <class 'frozenset'>

⚠️重要：{}创建的是空字典，不是空集合！空集合必须用set()。

2.2 添加与删除元素

s={1,2,3}# ─── 添加元素 ───# add()：添加单个元素s.add(4)print(s)# {1, 2, 3, 4}s.add(3)# 添加重复元素，无效果print(s)# {1, 2, 3, 4}# update()：添加多个元素（可迭代对象）s.update([5,6])# 添加列表s.update({7,8})# 添加集合s.update((9,10))# 添加元组s.update("ab")# 添加字符串 → 添加 'a', 'b'print(s)# {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 'a', 'b'}# ─── 删除元素 ───s={1,2,3,4,5}# remove()：删除指定元素，不存在则报错s.remove(3)print(s)# {1, 2, 4, 5}# s.remove(10) # KeyError: 10# discard()：删除指定元素，不存在不报错（推荐）s.discard(4)# 成功删除s.discard(10)# 静默忽略，不报错# pop()：随机删除并返回一个元素item=s.pop()print(f"弹出:{item}, 剩余:{s}")# clear()：清空集合s.clear()print(s)# set()

2.3 查询与遍历

s={'Python','Java','Go','Rust'}# 成员检测（集合最强功能！）print('Python'ins)# True ← O(1)print('C++'ins)# False ← O(1)# 遍历（无序！）forlangins:print(lang)# 输出顺序不确定：可能是 Go, Java, Python, Rust...# 长度print(len(s))# 4# 判断空集print(bool(s))# Trueprint(bool(set()))# False

3. 集合运算：数学之美

集合最优雅的地方在于它直接支持数学集合运算。

数学符号 vs Python 运算符： A ∪ B (并集) → A | B 或 A.union(B) A ∩ B (交集) → A & B 或 A.intersection(B) A - B (差集) → A - B 或 A.difference(B) A △ B (对称差) → A ^ B 或 A.symmetric_difference(B) A ⊆ B (子集) → A <= B 或 A.issubset(B) A ⊇ B (超集) → A >= B 或 A.issuperset(B)

3.1 并集：合并去重

frontend={'HTML','CSS','JavaScript','React'}backend={'Python','Java','SQL','JavaScript'}# 并集：所有技能（去重）all_skills=frontend|backendprint(all_skills)# {'HTML', 'CSS', 'JavaScript', 'React', 'Python', 'Java', 'SQL'}# 等价写法all_skills=frontend.union(backend)

3.2 交集：共同元素

# 交集：前后端都会的技能common=frontend&backendprint(common)# {'JavaScript'}# 等价写法common=frontend.intersection(backend)

3.3 差集：独有元素

# 差集：仅前端会的only_frontend=frontend-backendprint(only_frontend)# {'HTML', 'CSS', 'React'}# 差集：仅后端会的only_backend=backend-frontendprint(only_backend)# {'Python', 'Java', 'SQL'}# 对称差集：仅一方会的（不会双方都有的）exclusive=frontend^backendprint(exclusive)# {'HTML', 'CSS', 'React', 'Python', 'Java', 'SQL'}

3.4 子集与超集

skills={'Python','SQL','Linux'}backend_must={'Python','SQL'}# 子集判断print(backend_must<=skills)# Trueprint(backend_must.issubset(skills))# True# 超集判断print(skills>=backend_must)# Trueprint(skills.issuperset(backend_must))# True# 真子集（严格子集）print(backend_must<skills)# True（skills 更大）print(skills<skills)# False（不是真子集）# 不相交判断print({'A','B'}.isdisjoint({'C','D'}))# True（无共同元素）

3.5 运算可视化

frontend = {HTML, CSS, JS, React} backend = {Python, Java, SQL, JS} ┌─────────────────────────────┐ │ 并集 frontend | backend │ │ {HTML, CSS, JS, React, │ │ Python, Java, SQL} │ │ ┌───┐ │ │ {JS} │ │ │ │ 交集 │ │ │ │ └───┘ │ │ 仅前端 仅后端 │ │ {HTML,CSS, {Python,Java, │ │ React} SQL} │ └─────────────────────────────┘

4. 集合的底层原理

4.1 基于哈希表实现

Python 的set和dict一样，底层都是哈希表（Hash Table）。

哈希表原理： 键(key) → 哈希函数 → 哈希值 → 取模 → 数组索引 ↓ ┌─────────┐ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ └─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┘ │ │ │ │ │ │ None 42 None 17 None 99 查找 42：hash(42) % 6 = 1 → 直接访问索引1 → O(1)

4.2 为什么集合元素必须可哈希？

# ✅ 可哈希元素（不可变类型）s={1,"hello",(1,2),frozenset([3,4])}# ❌ 不可哈希元素（可变类型）# s = {[1, 2]} # TypeError: unhashable type: 'list'# s = {{1, 2}} # TypeError: unhashable type: 'set'# s = {{"a": 1}} # TypeError: unhashable type: 'dict'# 原理：哈希值必须稳定，可变对象哈希值会变

4.3 集合 vs 列表 vs 字典

5. 集合在算法中的应用

5.1 两数之和（哈希优化版）

deftwo_sum(nums:list[int],target:int)->list[int]:""" 用集合/字典优化：从 O(n²) 降到 O(n) """seen=set()fori,numinenumerate(nums):complement=target-numifcomplementinseen:# O(1) 查找！return[nums.index(complement),i]seen.add(num)return[]# 测试print(two_sum([2,7,11,15],9))# [0, 1]print(two_sum([3,2,4],6))# [1, 2]

5.2 判断数组是否有重复元素

defcontains_duplicate(nums:list[int])->bool:"""利用集合去重特性"""returnlen(nums)!=len(set(nums))# 测试print(contains_duplicate([1,2,3,4]))# Falseprint(contains_duplicate([1,2,3,3]))# True

5.3 寻找两个数组的交集

defintersection(nums1:list[int],nums2:list[int])->list[int]:""" 求两个数组的交集（去重） 方法1：集合运算（推荐） """returnlist(set(nums1)&set(nums2))defintersection_v2(nums1:list[int],nums2:list[int])->list[int]:""" 方法2：遍历较小集合，检测是否在另一个集合中 适合一个数组很大，一个很小的情况 """iflen(nums1)>len(nums2):nums1,nums2=nums2,nums1# 保证 nums1 较小set2=set(nums2)return[xforxinset(nums1)ifxinset2]# 测试print(intersection([1,2,2,1],[2,2]))# [2]print(intersection_v2([4,9,5],[9,4,9,8,4]))# [9, 4]

5.4 最长连续序列

deflongest_consecutive(nums:list[int])->int:""" 最长连续序列 思路：用集合 O(1) 查找，只从序列起点开始计数 时间：O(n)，空间：O(n) """num_set=set(nums)longest=0fornuminnum_set:# 只从序列的起点开始（num-1 不在集合中）ifnum-1notinnum_set:current_num=num current_streak=1whilecurrent_num+1innum_set:current_num+=1current_streak+=1longest=max(longest,current_streak)returnlongest# 测试print(longest_consecutive([100,4,200,1,3,2]))# 4 ([1,2,3,4])print(longest_consecutive([0,3,7,2,5,8,4,6,0,1]))# 9

5.5 单词拆分

defword_break(s:str,word_dict:list[str])->bool:""" 判断字符串能否被拆分成字典中的单词 用集合加速查找 """word_set=set(word_dict)n=len(s)dp=[False]*(n+1)dp[0]=True# 空字符串可被拆分foriinrange(1,n+1):forjinrange(i):ifdp[j]ands[j:i]inword_set:# O(1) 查找dp[i]=Truebreakreturndp[n]# 测试print(word_break("leetcode",["leet","code"]))# Trueprint(word_break("applepenapple",["apple","pen"]))# Trueprint(word_break("catsandog",["cats","dog","sand","and","cat"]))# False

6. 性能对比与最佳实践

6.1 成员检测性能对比

importtimedefbenchmark():"""对比列表和集合的成员检测性能"""# 准备数据n=100000data=list(range(n))target=n-1# 最后一个元素（最坏情况）# 列表查找start=time.time()for_inrange(1000):found=targetindata# O(n)list_time=time.time()-start# 集合查找data_set=set(data)start=time.time()for_inrange(1000):found=targetindata_set# O(1)set_time=time.time()-startprint(f"数据量:{n}")print(f"列表查找 1000 次:{list_time:.4f}秒")print(f"集合查找 1000 次:{set_time:.4f}秒")print(f"集合快{list_time/set_time:.0f}倍")benchmark()

典型输出：

数据量: 100000 列表查找 1000 次: 2.3456秒 集合查找 1000 次: 0.0001秒 集合快 23456 倍

6.2 去重性能对比

importrandomdefdedupe_benchmark():"""对比不同去重方法的性能"""data=[random.randint(0,10000)for_inrange(100000)]# 方法1：列表遍历（O(n²)）importtime start=time.time()result=[]forxindata:ifxnotinresult:result.append(x)t1=time.time()-start# 方法2：集合去重（O(n)）start=time.time()result=list(set(data))t2=time.time()-start# 方法3：dict.fromkeys（保持顺序，Python 3.7+）start=time.time()result=list(dict.fromkeys(data))t3=time.time()-startprint(f"列表遍历:{t1:.4f}秒")print(f"集合去重:{t2:.4f}秒")print(f"字典去重:{t3:.4f}秒")dedupe_benchmark()

6.3 最佳实践

# ✅ 推荐用法# 1. 快速去重unique=list(set(original_list))# 2. 成员检测（大量查询时）ifiteminsome_set:# 比 list 快得多# 3. 集合运算替代循环common=set(a)&set(b)# 比双重循环优雅# 4. 过滤重复seen=set()foriteminitems:ifitemnotinseen:seen.add(item)process(item)# ❌ 避免用法# 1. 不要依赖集合顺序（虽然 Python 3.7+ 有插入顺序，但不保证）# 需要有序用 dict.fromkeys() 或 sorted()# 2. 不要存储可变对象# bad_set = {[1, 2]} # TypeError# 3. 小数据量没必要转集合# 10个元素的列表，in 操作也很快

7. 总结

7.1 核心要点速查

7.2 集合使用场景

什么时候用集合？ ├── 需要去重 │ └── list → set → list ├── 频繁成员检测 │ └── if x in container: 用 set 替代 list ├── 集合运算 │ └── 交集、并集、差集等数学运算 ├── 过滤重复 │ └── 配合 seen 集合记录已处理元素 └── 算法优化 └── 用 O(1) 查找替代 O(n) 查找

7.3 与列表、字典的关系

┌─────────────┐ │ 可变容器 │ └──────┬──────┘ │ ┌─────────┼─────────┐ │ │ │ ▼ ▼ ▼ list set dict (有序) (无序) (键值对) 可重复 不重复 键不重复 O(n)查找 O(1)查找 O(1)查找