题目链接：
最近在leetcode刚好刷到这一系列的题目，所以打算一次性搞明白。我在面试时遇到了一道类似的题，只是设置稍作变化。当时虽然思路答对了，但是实现细节还没有搞明白。在这里一次性解决，下面按照复杂程度来递进地解决。
Base
这道题的基本设置是这样：
1个数组，所有数字都出现2次，只有1个数字只出现1次，找出这个数字。要求：时间复杂度O(n)，空间复杂度O(1)。
这个复杂度要求我们最高效地解决问题，只要见过这道题，就会知道最好地方法是异或！将所有数字异或后得到地结果直接就是我们要的数字！
变体
接下来在基础题目的基础上，考虑一下变体：
我遇到的面试原题
1个数组，按顺序存储。所有数字都出现2次，只有1个数字只出现1次，找出这个数字。要求：时间复杂度O(logn)，空间复杂度O(1)。
这道题不仔细看以为一样，唯一的变化就是数组是有顺序存储的并且时间复杂度的要求更近一步，需要达到O(logn)，又有顺序存储，又是logn，找到思路并不难，解法和位计算无关！就是二分查找！
想写二分查找必须得搞明白，我们怎么确定每次遍历减半的条件？我们要充分利用奇偶性！
对于只出现一次的数字，它之前一定有偶数位，之后也一定有偶数位，官方题解有序数组中的单一元素提供了两种思路：
- 判断mid是否在偶数位，并和相邻元素比较
- 只在偶数位的mid做判断
即便知道了利用奇偶性、判断条件，更新left和right我感觉还是比较难，这个时候应当对着一个例子来做：
[1,1,2,3,3,4,4,8,8]
对于奇数位，我们想要比较的是它的前一位和它，因为它的后一位肯定与它不同。即：nums[mid-1]=nums[mid]。在不等于时说明在这个位置之前，整个数组的奇偶性已经变了，说明扰乱秩序的那个单独数字就在前半部分。
对于偶数位，我们想要比较的是它和它的后一位，即：nums[mid]==nums[mid+1]，如果出现不想等则说明有两种情况：
- 这位数字就是我们要找的结果，那个单独的数字
- 在这个数字之前奇偶性就被打乱，单独数字在之前部分。
我把自己写的代码放到这里：
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int n=nums.size();
int left=0,right=n-1;
while(left<right){
int mid=(left+right)/2;
if(mid%2==1){
if(nums[mid-1]!=nums[mid])
right=mid-1;
else
left=mid+1;
}
else{
if(nums[mid]!=nums[mid+1])
right=mid;
else
left=mid+1;
}
}
return nums[left];
}
};
PS：今天整理这一系列题目才发现，原来这道题我在面试前曾经做过，但是面试上遇到也完全不记得。原题并不是Hot 100题，没有反复练，所以作为笨鸟，真的要多飞几遍。
有2个单独数字
leetcode上还有这么一个变体：
1个数组。所有数字都出现2次，有2个数字只出现1次，找出这2个数字。要求：时间复杂度O(n)，空间复杂度O(1)。
我们想把之前的经验迁移过来，但是一旦有两个数字异或的方法就失效了，我们可以动动脑筋，类似二分，我们把数组分为两组，一组恰好有1个单独数字，这样就可以用异或求出2个组的数字了。那么关键在于如何分组？
我们依然利用异或的性质，在这种情况下我们全部异或得到的会是$a\oplus b$，每一位数字1表示a, b不同，0表示a, b相同。我们只要任选一位为1的位置和所有数做&操作，自然就分为两组并且可以保证a和b在两个组。代码我贴在下面：
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
//注意溢出的问题，最好用unsigned
unsigned ret=0;
for(int n:nums){
ret^=n;
}
unsigned d=1;
//这里选择的是用最高位的1
while(ret>1){
ret>>=1;
d<<=1;
}
int a=0,b=0;
for(int n:nums){
if(n&d){
a^=n;
}
else{
b^=n;
}
}
vector<int> ans{a,b};
return ans;
}
};
重复3遍
1个数组。所有数字都出现3次，只有1个数字只出现1次，找出这个数字。要求：时间复杂度O(n)，空间复杂度O(1)。
之前的题目都是重复两遍，变为重复三遍会导致异或失效，我们依然可以利用位计算，将每一位的数值相加，无法被3整除的位一定是单独数字的位。具体怎么实现可以看下代码：
class Solution {
public:
int singleNumber(vector<int>& nums) {
vector<int> bitsum(32,0);
for(int n:nums){
//这里要注意mask可能溢出
long mask=1;
for(int i=31;i>=0;i--){
if(n&mask)
bitsum[i]++;
mask<<=1;
}
}
int res=0;
for(int i=0;i<32;i++){
//要先左移，否则最后会多做一次左移操作
res<<=1;
if(bitsum[i]%3!=0)
res+=bitsum[i]%3;
}
return res;
}
};