[剑指offer]-数组中只出现一次的两个数字
题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
知识补充：
异或是一种基于二进制的位运算，用符号XOR或者 ^ 表示，其运算法则是对运算符两侧数的每一个二进制位，同值取0，异值取1。它与布尔运算的区别在于，当运算符两侧均为1时，布尔运算的结果为1，异或运算的结果为0。
简单理解就是不进位加法，如1+1=0，,0+0=0,1+0=1。
性质
1、交换律
2、结合律（即(a^b)^c == a^(b^c)） 重点！！！
3、对于任何数x，都有x^x=0，x^0=x
4、自反性 A XOR B XOR B = A xor 0 = A
思路：
要求时间复杂度是O(n)，空间复杂度是O(1)。
大家首先想到的是顺序扫描法，但是这种方法的时间复杂度是O（n^2）。接着大家又会考虑用哈希表的方法，但是空间复杂度不是O（1）。
我们知道异或的一个性质是：任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字。比如数组{4,5,5}，我们先用数组中的第一个元素4（二进制形式：0100）和数组中的第二个元素5（二进制形式：0101）进行异或操作，0100和0101异或得到0001，用这个得到的元素与数组中的三个元素5（二进制形式：0101）进行异或操作，0001和0101异或得到0100，正好是结果数字4。这是因为数组中相同的元素异或是为0的，因此就只剩下那个不成对的孤苦伶仃元素。
现在好了，我们已经知道了如何找到一个数组中找到一个只出现一次的数字，那么我们如何在一个数组中找到两个只出现一次的数字呢？如果，我们可以将原始数组分成两个子数组，使得每个子数组包含一个只出现一次的数字，而其他数字都成对出现。这样，我们就可以用上述方法找到那个孤苦伶仃的元素。
我们还是从头到尾一次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数组的异或结果。因为其他数字都出现了两次，在异或中全部抵消了。由于两个数字肯定不一样，那么异或的结果肯定不为0，也就是说这个结果数组的二进制表示至少有一个位为1。我们在结果数组中找到第一个为1的位的位置，记为第n位。现在我们以第n位是不是1为标准把元数组中的数字分成两个子数组，第一个子数组中每个数字的第n位都是1，而第二个子数组中每个数字的第n位都是0。
举例：{2,4,3,6,3,2,5,5}
我们依次对数组中的每个数字做异或运行之后，得到的结果用二进制表示是0010。异或得到结果中的倒数第二位是1，于是我们根据数字的倒数第二位是不是1分为两个子数组。第一个子数组{2,3,6,3,2}中所有数字的倒数第二位都是1，而第二个子数组{4,5,5}中所有数字的倒数第二位都是0。接下来只要分别两个子数组求异或，就能找到第一个子数组中只出现一次的数字是6，而第二个子数组中只出现一次的数字是4。
思路总结：
本文思路有两大亮点：
【1】一个整数数组中如果除了其中一个数以外，其他数都出现了两次，将这些数相异或得到的是这个单一的数。
【2】如何将两个单一的数字分到两批数中，将所有数异或，得到的结果其实就是两个单一数字的异或结果，根据其中某一位是否为1将两个数字分开，其他数字也根据这个标准分成了两批。 最终分成的两批数字中，每一批数字中，只有一个单一数字。
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
int len = data.size();
if(len < 2)
return;
//对原始数组每个元素依次求异或(异或为位运算)
int temp=0;
for(int i=0;i<len;i++)
temp ^= data[i];
int indexOf1 = rfindFirst1(temp);
*num1 =0;
*num2 =0;
for(int i=0;i<len;i++){
if(isBit1(data[i],indexOf1))
*num1 ^=data[i];
else
*num2 ^=data[i];
}
}
private:
//从右找到某个数二进制形式下第一次出现1的下标
int rfindFirst1(int num){
int bit1 = 1;
int index =0;
while((num & bit1)== 0 && (index < 8*sizeof(int))){
bit1 = bit1<<1;
index++;
}
return index;
}
//判断某个数index位是否为1
bool isBit1(int num,int index){
num = num>>index;
return (num & 1);
}
};
二刷的时候，最终对每个数移位的时候不是通过对该数移动、位之后再判断其是否为1，而是直接通过位与，直接判断相应位是否为1，但是遇见了个大坑！！！
直接写 a & flag != 0;会判断错误
经验教训！！！，该多加个括号的时候不要吝啬！！！！
class Solution {
public:
void FindNumsAppearOnce(vector<int> data, int* num1, int *num2) {
int len = data.size();
if (len < 2)
return;
int temp = 0;
for (int i = 0; i < len; i++) {
temp ^= data[i];
}
int flag = 1;
while ((temp & flag) == 0) {
flag = flag << 1;
}
*num1 = 0;
*num2 = 0;
for (int i = 0; i < len; i++) {
//bool aa = isfalag1(data[i], flag);
if (isfalag1(data[i], flag)) {
*num1 ^= data[i];
cout << "第1组" << data[i] << endl;
}
else {
*num2 ^= data[i];
cout << "第2组" << data[i] << endl;
}
}
}
//通过与flag相位与，判断每个数相对于temp中从右到左的第一个为1的位是否为1
bool isfalag1(int a, int flag) {
if ((a & flag) != 0) //大坑！！！直接写 a & flag != 0;会判断错误
return true;
else
return false;
}
};