《剑指Offer》-51-数组中数字出现的次数
数组中除了两个数字，其他数字都出现了两次，找出这两个只出现了一次的数字
判断一个数字出现过没有，我们最常用的就是 set，set 中存在，那么就说明已经出现过了
但是这里要求空间复杂度O(1)，所以得换个思路
于是我想到了排序，将数组排序后相同的两个重复元素肯定是相邻的，这样我们只需要一次遍历就能够找出只出现一次的元素了
但是哪怕是性能最优的排序，时间复杂度也是O(N logN)，仍然不满足题目要求，肯定还有更好的办法
数组元素大小没有限定，用不了数组下标；双指针也不合适……
翻书，面试官提示：假如只考虑只有一个只出现一次的数字，你会怎么做？
本题的关键在于 发散
还是不知道，有什么区别吗
答案揭晓
用异或，将数组中所有的元素依次异或，根据：
- 相同元素异或得 0
- 0 异或任何元素等于元素本身
这样就能得到唯一一个只出现了一次的数字
那么拓展到出现了两个呢？两个只出现一次的数字肯定就不能再向上面那样简单粗暴了
我还是想不到
题目给出的做法是：将数组分开为两个数组。每个子数组中包含了一个只出现了一次的数字，区分的标准则是全部异或得到的数字的二进制表示中第一个为 1 的位置，在原始数组元素的二进制表示中是否为 1，很绕
vector<int> singleNumbers(vector<int>& nums) {
unsigned int res = nums[0];
for (int i = 1; i < nums.size(); i++) {
res ^= nums[i];
}
int indexBit = 0;// 计数，从右往左第几位
// 怎么找二进制表示中最右边的1？&1==0代表了什么，代表是偶数，即最右边不是1
while ((res & 1) == 0 && indexBit < 8 * sizeof(int)) {
res = res >> 1;
++indexBit;
}
int num1=0, num2=0;
for (int num : nums) {
if ((num >> indexBit) & 1) num1 ^= num;
else num2 ^= num;
}
return { num1,num2 };
}