19 . 只出现一次的数字
题目介绍
给你一个非空整数数组nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
提示：
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104- 除了某个元素只出现一次以外，其余每个元素均出现两次。
class Solution { public: int singleNumber(vector<int>& nums) { } };全文1300字，阅读+思考 8min
原题链接：136. 只出现一次的数字 - 力扣（LeetCode）
解析
1 . 本题需求很简单，即给你一个数组(vector<int>) ，找出数组中只出现一次的数字并返回
且其余数字都出现了两次
哈希
1 . 对于要找出单身狗数字，很容易想到的思路：遍历数组一遍，统计每个数字出现的次数
2 . 只需要统计一遍，就能知道每个数字出现多少遍。
代码初步构建：
class Solution { public: int singleNumber(vector<int>& nums) { map<int,int> mp;// 数字 ，出现的次数 for(auto e:nums) { mp[e]++; } //统计完毕 } };3 . 已经统计好每个数字出现的次数，那么再遍历一遍数组
4 . 一旦遇到次数为1（即mp[e] == 1)就立刻返回e
class Solution { public: int singleNumber(vector<int>& nums) { map<int,int> mp;// 数字 ，出现的次数 for(auto e:nums) { mp[e]++; } for(auto e:nums) { if(mp[e] == 1) return e; } return 0;//为了编译通过，需要再加一个return } };注：
1 . 这个方法逻辑和写法没有问题
2 . 可使用了O(n)的空间开销而非常量，但时间开销符合要求O(n)
异或
此方法重点掌握——
1 . 回忆：异或。全称：按位异或——二进制位运算之一
2 . 异或的本质 ： 模二乘法运算
a . 0 ^ 0 = 0 0 ^ 1 = 1 1^1 = 0
b . a ^ 0 = a a ^ a = 0;
3 . 我们正是利用”b中式子”完成需求
a . 当给出的数组都是成双成对的数字，那么可想而知：将所有数字进行异或结果为0
b , 异或运算与顺序无关，它只与参与运算的位有关
c . 当数组中出现唯一一个单身狗数字，那么 0 ^ singleDog == singleDog
d. 所以：这个singleDog就是将所有数组异或之后的结果
代码呼之欲出：
class Solution { public: int singleNumber(vector<int>& nums) { int sigledog = 0;// 设置单身狗的初始值为0，因为0和任何数异或都保持为该数 for(auto& e:nums) { sigledog ^= e; } return sigledog; } };总结以及完整参考代码
class Solution { public: int singleNumber(vector<int>& nums) { map<int,int> mp;// 数字 ，出现的次数 for(auto e:nums) { mp[e]++; } for(auto e:nums) { if(mp[e] == 1) return e; } } };class Solution { public: int singleNumber(vector<int>& nums) { int sigledog = 0;// 设置单身狗的初始值为0，因为0和任何数异或都保持为该数 for(auto& e:nums) { sigledog ^= e; } return sigledog; } };本周其他算法一见：
15 . 有效的括号-CSDN博客
16 . 买卖股票的最佳时机-CSDN博客
17 . 爬楼梯-CSDN博客
18 . 杨辉三角-CSDN博客
20 . 多数元素-CSDN博客
赶快动起手来吧