82. 落单的数
给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。
样例
给出 [1,2,2,1,3,4,3]，返回 4
典型思考：位运算中的异或运算
1、异或
异或运算的性质：
任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果即0与只出现一次的数字异或结果为只出现一次的数字，因为那些出现两次的数字全部在异或中抵消掉了。
异或在计算机中运行的机理：其实异或就是把整数的32位的0,1串当做整数0,1，对应位加和后，对2取余的结果，那么对于这样三个数的情况，一样的，可以用相同的方法，对应位的0,1相加，最后对3取余。得到的结果就是那个落单的数的二进制表示。然后恢复成整数即可。
class Solution {
public:
/**
* @param A : an integer array
* return : a integer
*/
int singleNumber(vector<int> &A) {
int x=0;//将x初始化为0，因为0与任何数异或都等于它本身
for (int i = 0; i < A.size(); i++) {
x ^= A[i];
}
return x;
}
};2、异或的机理，利用一个数组记录二进制每个位的和。将所有的数转换成二进制，因为是int类型，共32位。申请常数级（32位）的额外空间，然后每个数对应的位相加，最后对应位上的和模2。最后的结果就是单个数对应的二进制数。
class Solution {
public:
/**
* @param A: Array of integers.
* return: The single number.
*/
int singleNumber(vector<int> &A) {
// write your code here
int ans[32]={0};
// memset(ans, 0, sizeof(ans));//将ans数组清零
for(int i=0; i<A.size(); ++i){
for(int k=0; k<32; k++)
//其中A[i]>>k，意思为A[i]右移k位
//(A[i]>>k)&1就是读取A[i]>>k的最低位
ans[k] = (ans[k]+((A[i]>>k)&1))%2; }
//将结果恢复为整数
int ret = 0;
int base = 1;
for(int i=0; i<32; ++i){
ret += ans[i]*base;
base *= 2;
}
return ret;
}
};
程序解释：void *memset(void *s, int ch, size_t n);
memset：作用是在一段内存块中填充某个给定的值，它是对较大的结构体或数组进行清零操作的一种最快方法。
例如：要把一个char a[20]清零，一定是 memset(a,0,20);
83. 落单的数 II
给出3*n + 1 个的数字，除其中一个数字之外其他每个数字均出现三次，找到这个数字。
样例
给出 [1,1,2,3,3,3,2,2,4,1] ，返回 4
一次遍历，常数级的额外空间复杂度
思想：1、排序，然后再找只出现一次的数。（通过）快排时间复杂度O(nlogn)（每次partition是n，平均需要logn次），空间复杂度O(1)。
2、利用哈希表，这个最简单（通过）
3、利用随机算法，这个也简单(时间超出限制）
4、转换成二进制，同上
代码：快速排序
class Solution {
public:
/*
* @param A: An integer array
* @return: An integer
*/
int singleNumberII(vector<int> &A) {
// write your code here
sort(A.begin(),A.end());
int count=1,i;
for(i=1;i<A.size();i++)
{
if(A[i-1]==A[i])
count++;
else if(count==1)
return A[i-1];
else count=1;
}
return A[i-1];
}
};2、哈希表
class Solution {
public:
/*
* @param A: An integer array
* @return: An integer
*/
int singleNumberII(vector<int> &A) {
// write your code here
unordered_map<int,int>result;
int i;
for(i=0;i<A.size();i++)
result[A[i]]++;
for(i=0;i<A.size();i++)
if(result[A[i]]==1)
return A[i];
}
};3、随机化方法（时间超出限制）
class Solution {
public:
/*
* @param A: An integer array
* @return: An integer
*/
int singleNumberII(vector<int> &A) {
// write your code here
int n=A.size();
srand(unsigned(time(0)));
while(true)
{
int index=rand()%n;
int candiate=A[index];
int count=0;
for(int i=0;i<n;i++)
{
if(A[i]==candiate)
count++;
}
if(count==1)
return candiate;
}
}
};4、转换成二进制，利用一个数组记录二进制每个位的和
class Solution {
public:
/**
* @param A : An integer array
* @return : An integer
*/
int singleNumberII(vector<int> &A) {
// write your code here
int ans[32];
memset(ans, 0, sizeof(ans));
for(int i=0; i<A.size(); ++i){
for(int k=0; k<32; k++)
ans[k] = (ans[k]+((A[i]>>k)&1))%3;
}
int ret = 0;
int base = 1;
for(int i=0; i<32; ++i){
ret += ans[i]*base;
base *= 2;
}
return ret;
}
};
总结：上述四种方法，比较看来，哈希表更通用一些，且简单，转换二进制对这种题型通用，随机化方法次之（但容易超出时间限制），排序方法次之。
84. 落单的数 III
异或应用升级版：
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
分析：这是一道很新颖的关于位运算的面试题。
首先我们考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。
这个题目的突破口在哪里？题目为什么要强调有一个数字出现一次，其他的出现两次？我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现依次的数字，因为那些出现两次的数字全部在异或中抵消掉了。
有了上面简单问题的解决方案之后，我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中，包含一个只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办法就是分别求出这两个只出现一次的数字了。
分组依据：对于2*n+1个数字用异或就行了，而在此题将所有数异或之后得到的是两个落单的数的异或结果，没办法将结果拆分成两个落单的数。但因为两个落单数不同，所以肯定存在某个位k，使得两落单数在第k位上一个为0另一个为1，怎么找到这个k? 找异或结果中1出现的位置即可。只需找到最小的这个k，然后将在k位上为0的所有数做异或，其他的在k位为1的所有数也做另外的异或，这样最终可以得到两个落单的数。
上图将所有二进制数按照第3位是否为1分成两组。
现在我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。因此到此为止，所有的问题我们都已经解决。
基于上述思路，我们不难写出如下代码：