🧩 集合

为什么重要

集合能去除重复项，并提供平均 O(1) 的成员检测——这对许多数据结构与算法问题来说堪称完美。

核心思想

集合是一袋唯一、可哈希、无序的元素。来自学校的运算：| 并集，& 交集，- 差集，^ 对称差。

试一试

去重与成员检测：

nums = [1, 1, 2, 3, 3, 5, 5, 7]
unique = set(nums)
print(unique, "size:", len(unique))

print(5 in unique)   # O(1) average
print(9 in unique)

集合代数：

a = {"red", "green", "blue", "yellow"}
b = {"green", "blue", "purple"}
print("union        ", a | b)
print("intersection ", a & b)
print("a only       ", a - b)
print("xor          ", a ^ b)

一道经典的面试题——第一个重复出现的字符：

def first_repeat(s):
  seen = set()
  for ch in s:
      if ch in seen:
          return ch
      seen.add(ch)
  return None

for w in ["abcdea", "abcde", "swiss"]:
  print(w, "->", first_repeat(w))

核心方法

| 方法 | 作用 | 示例 | | --- | --- | --- | | add(x) | 添加一个 | st.add(3) | | update(iter) | 添加多个 | st.update([4,5]) | | remove(x) | 移除；不存在则报错 | st.remove(2) | | discard(x) | 安全移除 | st.discard(2) | | pop() | 移除任意一个 | st.pop() | | clear() | 移除全部 | st.clear() | | copy() | 浅拷贝 | st.copy() |

子集 / 超集检查

A <= B   # subset
A <  B   # proper subset
A >= B   # superset

集合推导式与 frozenset

squares = {x*x for x in range(5)}   # set comprehension
fs = frozenset([1, 2, 3])           # immutable, hashable set

快速检查

• 问： {} 是集合吗？ 答： 不是，它是字典。空集合请用 set()。

小练习

• 统计一个句子里不重复的单词数量。
• 检查一个列表是否有重复项。

该做与不该做

• 该做：成员检测时使用集合。
• 不该做：依赖集合的顺序。

常见错误

• 错误： 用 {} 表示空集合。 修正： 使用 set()。
• 错误： 期望集合有顺序。 修正： 如果顺序重要，请用列表。

关键要点

• 集合存储唯一、可哈希的元素；查找平均为 O(1)。
• 集合代数（|、&、-、^）流畅而快速。
• "我之前见过这个吗？" → 就用集合。
• frozenset 是不可变、可哈希的变体——可以做字典的键。