题目描述
给你一个数组，除了x,数组中每个元素出现2次,让你求解出这个x。
[leetcode136]https://leetcode.com/problems/single-number/
思路
- 使用hashMap是非常容易理解并求解的不再累述。
- 接下来就是我们的位操作，这一类题的一个通用的解法。
算法步骤
对这个数组的每一位进行异或，最后的结果就是那个单数来的数。
算法原理
异或操作满足：ab=ba,aa=0,0a=a
所以一趟异或操作之后，那些出现偶数次的数对结果的贡献就没有影响，这些所有的出现偶数次的数异或之后为0，而0与那个单独出现的数x异或之后就为x。
算法代码
public class Solution {
public int singleNumber(int[] nums) {
int res=0;
for(int i:nums)
res^=i;
return res;
}
}
算法原理很简单，实现也很简单。但这里需要注意的是，那些出现多次的必须是出现偶数次，不然这个算法就失效了，那么对于出现奇数次的怎么办呢？接下来拓展详细描述这一类题目的解法。
拓展一
[leetcode]https://leetcode.com/problems/single-number-ii/
这次数组中除了x外，每个元素出现3次，需要你找出x。注意到次数3为奇数了，上述方法失效。
思路
- 当然了也可以使用一个hash,类似于上题的hash解法，不用改动代码即可实现。当然了，这种解法很low。不在详述。
public class Solution {
public int singleNumber(int[] nums) {
Map<Integer,Integer> hashMap=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
if(!hashMap.containsKey(nums[i]))
hashMap.put(nums[i],1);
else
hashMap.put(nums[i],2);
}
for(int i=0;i<nums.length;i++){
if(hashMap.get(nums[i])==1)
return nums[i];
}
return -1;
}
}
- 使用位操作
接下来介绍三种使用位操作的方法，其实他们的本质是一样的。
位操作方法一
算法步骤
- 因为int是32位，所以我们考虑使用一个长度为32的数组，初始化为0。
- 记res为最后的结果，由于res也为32位的int，我们只需要确定，res的每一位为1还是0即可，所以这里使用了一个外层32次的循环，内层函数每执行一次，确定了res的一个比特位。
- 假设现在需要确定res的第i比特位，内层函数找出原数组中在第i比特位上为1的数，统计这些数的个数，然后对3取模，结果要么是0，要么是1(因为本题中那个特殊的数只出现一次)这个结果就是我们的res的第i比特位的值。
- 32趟走完时候我们可以确定res的每一个比特位是0还是是1，也就可以确定res的值了。
算法原理
因为原数组中除了数res外，每个数都出现三次，所以我考察这些数的对应比特位。那些出现三次的数，对应为1的比特位相加后为3的倍数，只有这个只出现1次的数的那些为1的bit位，这些位数上count为3n+1，所以我们相加取模时候就可以确定哪些比特位为1。
比如[1,2,2,2,3,3,3]
num a b
1 -> 0 1
2 -> 1 0
3 -> 1 1
2和3都出现了三次，所以我们把对应比特位1的个数相加的话a比特位一共6个1，b比特位一共4个1,对3取模后a比特为0，b比特位1。我们就知道结果为0。
算法代码
public class Solution {
public int singleNumber(int[] nums) {
int[] count=new int[32];
int res=0;
for(int i=0;i<32;i++){
for(int j=0;j<nums.length;j++){
if(((nums[j]>>i)&1)==1)
count[i]++;
}
res|=((count[i]%3)<<i);
}
return res;
}
}
//当然，一般化，假如出现多次的数出现次数为k，只需要模k即可。
//另外，如果那个特殊的数不是出现1次，
//修改res|=((count[i]%3)<<i)即可，
//例如假如出现2次，
//只需要修改为res|=((count[i]%3==0?0:1)<<i)
位操作方法二
算法步骤
- 使用三个变量，ones twos xthree，如果二进制表示中，某个数位上"1"出现一次，那么ones在这个数位上就是"1"，同理twos表示出现两次。
- 看看ones twos 的变化规则。新进来一个数nums[i]，考察ones&nums[i],如果ones在这个比特位上为1，表面之前这个比特位"1"出现过一次，现在nums[i]在这个比特位上又为1，那么自然就是出现了两次"1"，所以twos在这个比特位上就应该为1。ones的变化规则很简单，异或就行了。需要注意的是如果某个比特位在ones和twos中都为1,那么就代表出现了三次，需要把这个比特位清零。
- 遍历结束后，ones就是出现一次的数，twos就是出现两次的数。
算法原理
从比特位来考虑，出现三次的数在遍历结束之后对ones和twos都没有影响，因为他们最后会在他们比特位表示为"1"的位置上出现三次，他们的影响被代码
xthree = ~(ones & twos);
ones&=xthree;
twos&=xthree;
抹去，最后ones的各个比特位就是只出现一次的那个数的比特位，twos的各个比特位就是只出现两次的那个数的比特位。
算法代码
public class Solution {
public int singleNumber(int[] nums) {
//2,2,3,2
int ones=0;//二进制表示中“1”出现一次的数位
int twos=0;//二进制表示中“1”出现两次的数位
int xthree=0;
for(int i=0;i<nums.length;i++){
twos|=(ones&nums[i]);//出现两次，当然是“之前”位置上首先就是“1”（ones），然后输入的数树在这个位置上又是“1”
ones^=nums[i];//出现一次，当然是异或就行了，这样出现一次的变为0，出现0次的变为1
xthree = ~(ones & twos);//一个数位在ones和twos同时为1，表示当前数位出现了3次，应该把这个数位变为0
ones&=xthree;
twos&=xthree;
}
return ones;
}
}
//拓展，two最终记录的是出先两次的
//http://www.cnblogs.com/daijinqiao/p/3352893.html
//[1,2,2,2,3,3,4,4,4,5,5,5]
//[1,2,2,3,3,3,4,4,4,5,5,5]
位操作方法三
这个方法其实和方法二一样，只不过搞得有点像数电设计中的状态转移。
算法步骤&原理
a表示32位的int，a的每一位怎么确定，在遍历原数组过程中，考察原数组中数的比特位表示，如果该位上"1" 出现次数为2，那么该位就为1，否则为0
同理
a表示32位的int，b的每一位怎么确定，在遍历原数组过程中，考察原数组中数的比特位表示，如果该位上"1" 出现次数为1，那么该位就为1，否则为0
那么我们很容易得到下面的状态转移表
(ai为a的i比特位，bi为b的i比特位,ci为新遍历到的数的i比特位)
ai bi ci ai’ bi'
0 0 0 0 0
0 1 0 0 1
1 0 0 1 0
0 0 1 0 1
0 1 1 1 0
1 0 1 0 0
我们需要找到出现次数为1的比特位，也就是bi'为1
顺便找到出现次数为2的比特位，也就是ai'为1
所以ai'=aibici|~aibici
bi'=aibici|aibici
我们就可以确定出现次数为1的比特位，也就可以确定出现次数为1的数。
这里的代码是同时找了次数为1的和为2的（这种理解是特殊的数出现一次或两次，二者选其一）
算法代码
public class Solution {
public int singleNumber(int[] nums) {
int a=0;
int b=0;
for(int c:nums){
int tmpa=a&(~b)&(~c)|((~a)&b&c);
b=(~a&~b&c)|(~a&b&~c);
a=tmpa;
}
return a|b;
}
}
当然，如果了解转台转移化简的话,可以简化为
for(int c:nums){
int tmpa=a&(~c)|(b&c);
b=(~a&~b&c)|(b&~c);
a=tmpa;
}
拓展二
[leetcode260]https://leetcode.com/problems/single-number-iii/
这次是数组中有两个不同的数都只出现过一次，其他数都出现两次，让找出这两个数。
算法描述
- 对这些数进行异或操作得到ones
- 移位与操作得到once的比特位表示的第一个非“0”位置，并把一个数赋值为仅该位置为1，其他位置为0
- 用这个数去和数组中的数做与运算，根据与运算结果是否为0可以把原数组中的数分为两个阵营，分别对两个阵营进行异或操作，最终得到的两个结果就是所求的两个数。
算法原理
有两个数a,b只出现一次，其他两次，那么所有数进行异或之后的结果ones，ones比特位表示为1的位置肯定就是a和b在这个位置为一个1一个0，那么就可以使用这个位置把a和b分到不同的阵营中，两个阵营都是包含a/b和一堆成对出现的数，对他们进行异或操作即可求出a/b。
算法代码
public class Solution {
public int[] singleNumber(int[] nums) {
int one=0;
for(int i:nums)
one^=i;
int tmp=1;
while((one&1)!=1){
one>>=1;
tmp<<=1;
}
int res1=0;
int res2=0;
for(int i:nums){
if((i&tmp)==0){
res1^=i;
}
else
res2^=i;
}
int[] res=new int[2];
res[0]=res1;
res[1]=res2;
return res;
}
}
当然了，继续拓展的话，如果有两个数出现1次，其他书出现三次，那么就是拓展一中的方法先找到为出现次数为1的两个数共同影响产生的结果ones,然后找到一个为“1”的比特位，然后分阵营，就变为两个拓展一类型的问题。
如果一个一次一个两次其他三次，那么一次的就是ones,两次的就是twos。
