数据结构与算法|set以及set的典型运用数据结构|c++|set

set概述 set是根据元素值进行排序的集合，且集合中不存在重复元素。set是由二叉搜索树实现，且对树进行了平衡处理，使得元素在树中的分布较均匀，所以set中的插入、删除以及搜索操作的复杂度都是O(logn)。所在头文件为 < set> 。
set常用成员函数

begin() – 返回指向set开头的迭代器
end() – 返回指向set末尾的迭代器
size() – 返回set中的元素总数
clear() – 清空set中所有元素
erase(x) – 删除含有x的元素
insert(x) – 插入元素x
find(x) – 搜索与x相等的元素，并返回指向该元素的迭代器，若找不到与x相等的元素则返回末尾end()

set的典型应用题目描述
Kiana拿到了一个可以控制路灯的遥控器。她只需要在遥控器上输入一个编号，就可以改变该编号对应的那盏路灯的状态。在初始状态下所有的灯都是熄灭的。Kiana很喜欢这个遥控器，她胡乱地开关着那些路灯，直到某一刻她发现当前恰好只有一个路灯是亮的，她想知道正在亮着的是哪个路灯，可是那盏灯离她太远了，她看不清那盏灯的编号。还好遥控器保留了她所有的操作记录，请你根据她的操作记录推测出亮着的灯的编号。
输入描述
【数据结构与算法|set以及set的典型运用】第一行为一个整数n，代表共有n条操作记录
接下来一行有n个数，代表 n 个被操作的路灯编号 numi。
n < 1e6
num < 1e10
输出描述
输出为一个整数，即开着的灯的编号
解题技巧
由于使用数组存以及搜索不是爆时间就是爆内存，所以直接巧妙利用set中的函数解题。
C++代码

#include #include #include #define ll long long using namespace std; set s; int main(){ int n; cin>>n; while(n--){ ll x; scanf("%lld",&x); if(s.find(x)!=s.end()) s.erase(x); else s.insert(x); } cout<<*s.begin(); return 0; }

写在后面这道题还有另一种解法更为巧妙方便，利用异或运算符！！！

#include #include #define ll long long using namespace std; int main() { int n; cin >> n; ll ans = 0, x; while(n--) { scanf("%lld", &x); ans ^= x; } printf("%lld", ans); return 0; }