数学基础

集合概念源自数学中的集合论，Python集合支持交、并、差等数学运算。

元素要求

集合元素必须是不可变类型（如数字、字符串、元组），不能包含列表、字典等可变对象。

1. 无序性

集合中的元素没有固定顺序，每次输出时顺序可能不同。集合不支持索引操作。

colors = {"red", "green", "blue"}
print(colors)  # 可能输出: {'green', 'blue', 'red'}

2. 元素唯一性

集合自动去除重复元素，确保每个元素只出现一次。

numbers = {1, 2, 2, 3, 3, 3, 4}
print(numbers)  # 输出: {1, 2, 3, 4} (重复值被移除)

3. 可变性

集合是可变的，可以添加或删除元素，但集合元素本身必须是不可变的。

s = {1, 2, 3}
s.add(4)        # 添加元素
s.remove(2)     # 删除元素
print(s)        # 输出: {1, 3, 4}

4. 高效成员检测

基于哈希表实现，集合的成员检测操作(in)非常高效，时间复杂度为O(1)。

n = 1000000
large_set = set(range(n))
large_list = list(range(n))

# 集合查找快得多
%timeit -n 100 999999 in large_set   # 约 0.0001秒
%timeit -n 100 999999 in large_list  # 约 0.1秒

直接创建

# 使用花括号
s1 = {1, 2, 3, 4, 5}

# 注意：空集合必须用set()
empty_set = set()

从其他结构转换

# 从列表创建
list_to_set = set([1, 2, 2, 3, 4])

# 从元组创建
tuple_to_set = set((1, 2, 3, 3))

# 从字符串创建（得到字符集合）
str_to_set = set("hello")
# 输出: {'h', 'e', 'l', 'o'}

集合推导式

# 创建平方数集合
squares = {x**2 for x in range(10)}
# {0, 1, 4, 9, 16, 25, 36, 49, 64, 81}

# 带条件的集合推导式
even_squares = {x**2 for x in range(10) if x % 2 == 0}
# {0, 4, 16, 36, 64}

基本操作

s = {1, 2, 3}

# 添加元素
s.add(4)        # s: {1, 2, 3, 4}

# 删除元素
s.remove(2)     # s: {1, 3, 4}
s.discard(5)    # 安全删除（不存在不报错）

# 随机弹出元素
elem = s.pop()  # 随机移除一个元素

集合运算

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

# 并集
print(A | B)   # {1, 2, 3, 4, 5, 6}

# 交集
print(A & B)   # {3, 4}

# 差集
print(A - B)   # {1, 2}
print(B - A)   # {5, 6}

# 对称差集
print(A ^ B)   # {1, 2, 5, 6}

数据去重

最直接的应用：快速去除列表中的重复元素。

# 列表去重
duplicates = [1, 2, 2, 3, 4, 4, 5]
unique_list = list(set(duplicates))
# 结果: [1, 2, 3, 4, 5] (顺序可能不同)

关系测试

快速检查多个数据集之间的关系。

# 检查共同兴趣
alice_interests = {"阅读", "旅行", "编程"}
bob_interests = {"编程", "游戏", "音乐"}

common = alice_interests & bob_interests
# 共同兴趣: {"编程"}

成员快速检测

当需要频繁检查元素是否存在时，集合比列表高效得多。

# 有效词检查
valid_words = {"apple", "banana", "orange", "grape"}
user_input = "banaa"

if user_input in valid_words:
    print("有效输入")
else:
    print("无效输入")

时间复杂度

• 添加元素：O(1)
• 删除元素：O(1)
• 成员检测：O(1)
• 并集/交集：O(len(s)+len(t))
• 差集：O(len(s))

使用注意事项

• 集合只能包含不可变对象
• 集合本身是可变对象，不可作为字典键
• frozenset是不可变集合，可作为字典键
• 集合不支持索引和切片操作
• 集合比较时不考虑元素顺序