异或运算是解决“其余元素均出现两次、仅一个出现一次”问题的最优方法，时间o(n)、空间o(1)，但要求输入非空且满足成对前提；否则需用哈希表统计频次。
用异或运算（^）直接找唯一元素
异或运算是解决这个问题最简洁、高效的方式，前提是其他元素都恰好出现两次，只有一个出现一次。因为 a ^ a == 0，而 a ^ 0 == a，所以把所有元素异或起来，成对的会抵消，最后剩下那个唯一的数。
实操时注意：数组必须非空，且满足“其余元素均出现两次”的前提；否则结果无意义。
- 时间复杂度
O(n)，空间复杂度O(1)，比哈希表省空间 - 不依赖元素大小或正负，
int、unsigned int、甚至char都适用 - 不能用于“出现三次”或“出现偶数次但不全是两次”的情况——那得换思路
int findSingle(const vector<int>& nums) {
int res = 0;
for (int x : nums) res ^= x;
return res;
}</int>
当元素出现次数不规则时，用 std::unordered_map 统计频次
如果题目变成“找出只出现一次的元素，其余元素出现任意多次（如 3 次、5 次）”，异或就失效了，必须统计每个值的出现次数。
这时候 std::unordered_map<int int></int> 是最直接的选择，但要注意迭代器遍历和内存开销。
- 插入和查找平均
O(1)，总时间O(n)，但常数较大，实际可能比异或慢几倍 - 键类型必须支持哈希（
int、string等没问题；自定义结构体需提供hash和==） - 别忘了在循环后检查
it->second == 1，而不是== 0—— 这是新手常错的点
int findSingleWithMap(const vector<int>& nums) {
unordered_map<int int> cnt;
for (int x : nums) cnt[x]++;
for (const auto& p : cnt)
if (p.second == 1) return p.first;
return 0; // 理论上不会走到这里
}</int></int>
使用 std::set 或 std::multiset 的陷阱
有人想用 std::set 去重后对比大小，或用 std::multiset 插入再遍历计数——这两种做法都容易出错且低效。
-
std::set无法区分“出现一次”和“出现多次”，只能知道值存在与否，完全丢失频次信息 -
std::multiset::count()是线性复杂度，整段调用下来变成O(n²)，大数据量会超时 - 若误用
std::set<int></int>存所有元素再减去去重后的集合，逻辑上也站不住脚——没有对应差集操作
边界与类型问题：vector<int></int> 为空或含负数怎么办
异或方案对负数完全透明，因为它是按位运算，符号位也参与计算，不影响结果。但空数组必须提前判断，否则循环不执行，返回初值 0 就是错的。
- 空输入应抛异常或返回特殊值（如
std::optional<int></int>），不能默认返回0 - 若元素是
long long，确保用对应类型做异或，避免隐式截断 - 数组含指针或自定义对象？异或不再适用——指针异或结果不可预测，对象需重载
operator^（极少这么做）
真正难的不是写出来，而是看清题干里“其余元素是否严格成对”这个隐含条件；漏看这点，后面所有优化都是白忙。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
