Python数据结构背景知识之集合（Set）
摘要：本文深入解析Python中set数据结构及其在算法题中的应用。介绍了set的核心特性（无序性、唯一性、可哈希性限制）和五大类常用函数（添加、删除、查询、集合运算、转换），重点讲解了对称差集运算a^b的使用场景。
专栏其他内容：
一、set数据结构背景
算法题中，“去重”和“频繁判断元素是否存在”是高频需求，而我们最熟悉的列表（list），其查找操作的时间复杂度是O(n)——需要遍历整个列表才能确定元素是否存在，去重也需借助循环或字典，效率低下。
集合（set）的出现，正是为了解决这一痛点。它的底层基于哈希表（Hash Table）实现，核心逻辑的是：将元素通过哈希函数映射到哈希表的索引位置，若两个元素哈希值相同（即哈希冲突），则通过链表或红黑树解决。这种实现让set的核心操作（添加、删除、查找）平均时间复杂度均为O(1)，远优于list的O(n)，这也是刷题中优先用set处理去重和查找的核心原因。
二、set核心特性
set的所有特性都围绕“去重”“快速查找”设计：
-
无序性：元素无固定插入顺序，不支持索引和切片（这是与list、tuple的核心区别）。刷题中若需“有序去重”，需先通过set去重，再用sorted()排序（如
sorted(set(nums))），不可直接遍历set依赖顺序。 -
唯一性：自动去除重复元素，无论插入多少个重复值，set中仅保留一个。这是set最常用的特性，比如快速去除数组中的重复元素，一行代码即可实现：
unique_nums = set(nums)。 -
可哈希性限制：set中的元素必须是可哈希对象（如int、str、tuple），不可哈希对象（如list、dict）无法加入set。示例：
s = {1, 2}合法，s = {[1, 2]}会直接报错——刷题中若需存储多个值，可先将其转为tuple，再加入set。 -
支持集合运算：内置交集（&）、并集（|）、差集（-）、对称差集（^）等操作，无需手动循环判断，可快速处理“两个集合的关系”。
三、set常用函数
set的函数均围绕其“可变、唯一、无序”特性设计，核心分为「添加、删除、查询、集合运算、转换」5大类：
1. 添加类函数（动态补充元素）
-
set.add(x)：向集合中添加单个元素x（x必须是可哈希对象），若x已存在，不做任何操作（避免重复）。 示例：
s = {1, 2}，s.add(3)→{1, 2, 3}；s.add(2)→ 无变化。 -
set.update(iterable)：向集合中添加可迭代对象（如列表、元组、字符串）中的所有元素，自动去重。 示例：
s = {1, 2}，s.update([2, 3, 4])→{1, 2, 3, 4}。
2. 删除类函数（安全移除元素）
-
set.remove(x)：从集合中删除元素x，若x不存在，直接报错（KeyError）。 示例：
s = {1, 2, 3}，s.remove(2)→{1, 3}；s.remove(4)→ 报错。 -
set.discard(x)：从集合中删除元素x，若x不存在，不做任何操作（无报错）。 示例：
s = {1, 2, 3}，s.discard(2)→{1, 3}；s.discard(4)→ 无变化。 -
set.pop()：随机删除集合中的一个元素，并返回该元素（因set无序，无法指定删除位置，建议不要使用）。 示例：
s = {1, 2, 3}，s.pop()→ 可能返回1、2或3，删除后集合对应减少该元素。 -
set.clear()：清空集合中的所有元素，返回空集合。 示例：
s = {1, 2, 3}，s.clear()→set()。
3. 查询类函数（快速判断/统计）
-
len(set)：统计集合中元素的个数，与list、tuple的len()用法一致。 示例：
s = {1, 2, 3}，len(s)→ 3。 -
x in set：判断元素x是否在集合中，返回布尔值（True/False），平均时间复杂度O(1)。 示例：
s = {1, 2, 3}，2 in s→ True；4 in s→ False。
4. 集合运算类函数（处理两个集合关系）
-
set.intersection(set2)：返回两个集合的交集（等价于
set & set2），不修改原集合。 示例：s1 = {1, 2, 3}，s2 = {2, 3, 4}，s1.intersection(s2)→{2, 3}。 -
set.union(set2)：返回两个集合的并集（等价于
set | set2），不修改原集合，自动去重。 示例：s1 = {1, 2}，s2 = {3, 4}，s1.union(s2)→{1, 2, 3, 4}。 -
set.difference(set2)：返回set中存在、set2中不存在的元素（等价于
set - set2），不修改原集合。 示例：s1 = {1, 2, 3}，s2 = {2, 4}，s1.difference(s2)→{1, 3} -
set.symmetric_difference(set2)：返回两个集合中互不相同的元素（等价于
set ^ set2），不修改原集合。 示例：s1 = {1, 2, 3}，s2 = {2, 3, 4}，s1.symmetric_difference(s2)→{1, 4}。
5. 转换类函数（适配不同场景）
-
tuple(set) / list(set)：将集合转为元组或列表（注意：转换后无序）。 示例：
s = {3, 1, 2}，list(s)→[1, 2, 3]（顺序不固定）；tuple(s)→(1, 2, 3)。 【注：刷题中常用于“去重后需有序”的场景（如先转为set去重，再用sorted()排序，最后转为list）。】 -
set(iterable)：将可迭代对象（如列表、元组）转为集合，自动去重。 示例：
nums = [1, 2, 2, 3]，s = set(nums)→{1, 2, 3}。 【注：最高频的用法，快速实现数组去重。】
四、重点补充：集合的a^b运算
在set的集合运算中，a ^ b（对称差集）是高频且易与其他运算混淆的知识点，单独拆解详解，贴合LeetCode刷题场景，帮你彻底避开误区：
-
运算含义：
a ^ b表示「对称差集」，核心是返回“只在a中、或只在b中，不在两个集合的交集中”的所有元素，等价于(a - b) | (b - a)，也等价于a.symmetric_difference(b) -
核心特点：不修改原集合a和b，返回一个新的集合；结果中不包含a和b的公共元素，只保留两者的“独有元素”。
刷题高频示例：
示例1：基础用法——提取两个数组的独有元素 a = {1, 2, 3, 4}（对应数组[1,2,3,4]），b = {3, 4, 5, 6}（对应数组[3,4,5,6]） a ^ b → {1, 2, 5, 6}（1、2仅在a中，5、6仅在b中，3、4是公共元素，不保留）。
示例2：刷题实战场景——《两个数组的差异》 题目要求：给定两个整数数组nums1和nums2，返回所有不在两个数组中同时出现的元素，用集合运算快速求解： nums1 = [1,2,3,4]，nums2 = [3,4,5,6] s1 = set(nums1)，s2 = set(nums2) result = list(s1 ^ s2) → [1,2,5,6]
避坑点：
-
❌ 误区1：混淆
a^b与a|b——a|b是并集，保留a和b的所有元素（去重），包含公共元素；而a^b不包含公共元素，只保留独有元素。 -
❌ 误区2：认为
a^b会修改原集合——与所有set集合运算一致，a^b返回新集合，原集合a和b的元素不变，刷题中可放心使用，无需担心破坏原数据。 ✅ 技巧：刷题中若遇到“找两个集合的独有元素”“排除公共元素”的需求，优先用a^b，比(a - b) | (b - a)更简洁，代码可读性更高。
与其他相关运算的对比： a = {1, 2, 3, 4}，b = {3, 4, 5, 6}
a & b（交集）：只保留公共元素 → {3,4}
a | b（并集）：保留所有元素（去重） → {1,2,3,4,5,6}
a - b（差集）：只保留a的独有元素 → {1,2}
a ^ b（对称差集）：保留a和b的独有元素 → {1,2,5,6}
五、算法题高频用法
用法1：快速去重
场景：题目要求“去除重复元素”“时判断是否有重复元素”
def containsDuplicate(nums):
return len(set(nums)) != len(nums)解析：将数组转为set后，重复元素会被自动去除，若set长度与原数组不同，则存在重复元素，时间复杂度O(n)（遍历数组转为set），空间复杂度O(n)（存储set），是该题最简洁高效的解法。
用法2：快速查找（替代list的in操作，提升效率）
场景：需要频繁判断“某个元素是否存在”，用set的in操作替代list的in操作，将时间复杂度从O(n)降至O(1)。
def twoSum(nums, target):
s = set()
for i, num in enumerate(nums):
complement = target - num
if complement in s: # O(1)查找，比list的in操作快得多
return [nums.index(complement), i]
s.add(num)用法3：集合运算（处理两个数组的关系）
核心运算示例：
-
返回两个数组的公共元素，用交集运算：
def intersection(nums1, nums2): return list(set(nums1) & set(nums2))
-
返回nums1中存在、nums2中不存在的元素，用差集运算：
def difference(nums1, nums2): return list(set(nums1) - set(nums2))-
提取两个数组的独有元素：用对称差集运算
a^b，如前面的实战示例。
用法4：辅助去重（回溯/排列组合题目）
在递归遍历、多层循环等场景中，需要避免同一层级重复选择相同元素（如生成不重复的组合 / 排列），用集合存储当前层级已选元素，可自动去重，无需手动写复杂的重复判断逻辑。
场景 1：递归 / 回溯场景（同层级去重）
# 核心：用集合记录当前层级已选元素，避免重复
def demo_recursion_duplicate_removal():
# 初始化集合，仅作用于当前递归层
selected_in_layer = set()
# 遍历候选元素
for val in candidate_elements:
# 核心判断：元素已选过则跳过（去重关键）
if val in selected_in_layer:
continue
# 标记为已选，同层后续遍历不再选
selected_in_layer.add(val)
#后续逻辑……场景 2：列表遍历去重（保留首次出现顺序）
# 核心：用集合记录已出现元素，遍历列表时过滤重复值
original_list = [2, 1, 3, 2, 1, 4]
unique_list = []
seen = set()
for num in original_list:
# 核心判断：未出现过才保留
if num not in seen:
seen.add(num)
unique_list.append(num)
# 输出：[2, 1, 3, 4]（保留首次出现顺序）场景 3：多层循环去重（简化重复判断）
# 核心：用集合记录内层已处理的值，避免重复计算
data = [1, 2, 2, 3, 3, 3]
result = []
for i in range(len(data)):
# 每层循环初始化独立集合，仅去重当前层
processed = set()
for j in range(i+1, len(data)):
val = data[j]
if val in processed:
continue
processed.add(val)
# 后续业务逻辑（如组合、计算等）
result.append((data[i], val))
# 输出：[(1,2), (1,3), (2,3)]（无重复组合）所有片段的核心逻辑一致：
- 初始化空集合
seen/selected/processed； - 遍历元素时用
val in 集合判断是否已处理； - 未处理则执行业务逻辑，并将元素加入集合标记；
- 已处理则直接跳过，实现自动去重。
六、高频误区
-
❌ 误区1：依赖set的顺序——set是无序的，若刷题中需要“有序输出”，需先转为set去重，再用sorted()排序，示例：
sorted(set(nums))，不可直接遍历set后输出（顺序不确定，会导致答案错误）。 -
❌ 误区2：尝试将不可哈希对象加入set——list、dict无法作为set的元素，若需存储多个值（如坐标），可先转为tuple，示例：
s.add((1, 2))合法，s.add([1, 2])报错。 -
❌ 误区3：混淆remove()和discard()——remove(x)若x不存在会报错，discard(x)不会，刷题中优先用discard(x)，尤其是不确定元素是否存在的场景（如删除候选元素）。
-
❌ 误区4：过度使用set——set虽高效，但需额外占用内存（空间复杂度O(n)），若题目要求“空间复杂度O(1)”（如《删除有序数组中的重复项》进阶要求），则不可用set，需用双指针法。
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
32
0- 0
已为社区贡献2条内容
所有评论(0)