集合无序不重复的数据容器集合Set是一个简单但强大的数据结构它只关心有没有不关心排第几。今天来聊聊这个不重复的数据容器。一、什么是集合集合的概念来自数学一堆确定的、互不相同的对象组成的整体。在编程中集合有三个特点无序元素没有固定的排列顺序不重复每个元素只能出现一次可变部分实现可以添加和删除元素集合A {1, 2, 3, 4, 5} 集合B {4, 5, 6, 7, 8}二、生活中的例子朋友圈你微信通讯录里的人就是一个集合——每个人只能出现一次不会有两个张三在你通讯录里联系人之间也没有先后顺序。去重你有一堆数据要去重放进集合自动就不重复了输入[1, 2, 2, 3, 3, 3, 4]集合{1, 2, 3, 4}权限列表一个用户有哪些权限用集合存user_permissions {read, write, delete}判断用户有没有某个权限O(1) 搞定三、集合的核心操作基本操作操作时间复杂度说明添加平均 O(1)set.add(x)删除平均 O(1)set.remove(x)查找平均 O(1)x in set集合运算重点并集两个集合的所有元素合在一起A ∪ B {1, 2, 3, 4, 5, 6, 7, 8}交集两个集合共有的元素A ∩ B {4, 5}差集在A中但不在B中的元素A - B {1, 2, 3} B - A {6, 7, 8}对称差集在A或B中但不同时在两者中的元素A △ B {1, 2, 3, 6, 7, 8}四、代码示例Python 的 setA{1,2,3,4,5}B{4,5,6,7,8}# 并集print(A|B)# {1, 2, 3, 4, 5, 6, 7, 8}print(A.union(B))# 交集print(AB)# {4, 5}print(A.intersection(B))# 差集print(A-B)# {1, 2, 3}print(A.difference(B))# 对称差集print(A^B)# {1, 2, 3, 6, 7, 8}Java 的 HashSetSetIntegersetnewHashSet();set.add(1);set.add(2);set.add(2);// 重复不添加System.out.println(set.size());// 2System.out.println(set.contains(1));// true五、集合的底层实现和字典一样集合底层通常也是哈希表只存键不存值或者说值部分无所谓添加元素 在哈希表中插入键查找元素 在哈希表中查找键所以集合的查找速度和哈希表一样平均 O(1)。有些语言也提供有序集合如 C 的std::set底层是红黑树查找 O(log n)但元素有序。六、集合的经典应用1. 去重names[张三,李四,张三,王五,李四]unique_nameslist(set(names))# [张三, 李四, 王五]2. 成员检测vip_users{张三,李四,王五}if张三invip_users:print(是VIP)# O(1) 快速判断3. 共同好友friends_A{张三,李四,王五}friends_B{李四,王五,赵六}commonfriends_Afriends_B# 交集# {李四, 王五}4. 图的BFS去重visitedset()# 记录访问过的节点queue[start_node]whilequeue:nodequeue.pop(0)ifnodeinvisited:continuevisited.add(node)# 处理节点...七、集合 vs 数组 vs 字典特性集合数组字典有序性无序有序通常无序重复性不允许允许键不允许访问方式判断存在按下标按键查找速度O(1)O(n)O(1)用途去重、成员判断顺序存储键值映射八、软考常考点考点1集合的特点无序、不重复底层通常是哈希表考点2集合运算并集、交集、差集的计算用文氏图Venn Diagram表示考点3时间复杂度添加、删除、查找平均 O(1)考点4应用场景去重、成员判断、集合运算软考小贴士集合的核心是无序不重复。考试常考集合运算并交差以及集合与数组、字典的区别。记住集合擅长快速判断在不在。一句话记住集合 不重复的无序容器底层是哈希表查找O(1)擅长去重和成员判断。互动时间你在编程中用集合最多的场景是什么去重还是做交并集运算评论区聊聊点赞收藏转发给学编程的朋友关注「通俗易懂学IT」数据结构逐个击破知识星球助你系统学习计算机知识备考资料真题解析学习打卡扫码加入