PRoblem 1：一个数组中有一个数字a只出现一次，其他数字都出现了两次。请找出这个只出现一次的数字？
考察知识点：异或运算
思路：比如数字 b^b = 0
a^0 = a
因此，可以将数组中的所有数字进行异或，而最终异或的结果即为所求只出现一次的数字a.
代码：
1defSingleNumber1(Array):2ret =03foriinArray:4ret ^=i5returnret
==========================================================
Problem 2：一个数组中有一个数字a只出现一次，其他数字都出现了三次。请找出这个只出现一次的数字？
考察知识点：位运算
解法一：
考虑用统计的思路来解这道题，如果一个数出现了三次就消掉，int的32个位都是由0/1组成的，所以将所有数的对应位加起来，
再将各位的统计和对3取模，最终剩下的结果就是要找出的数。
例如：数组 [4 7 4 4](这里为了方便，我们取int的最后四位)
40100
70111
40100
40100
Sum 0411
Sum%3 0111
最后Sum%3得到的结果0111即7，就是我们所要求的Single Number
代码：
1defSingleNumber2_1(Array):2ret =03foriinrange(0,32):4c =05d = 1 <<i6forjinrange(0, len(Array)):7ifArray[j] &d:8c += 19ifc % 3:10ret |=d;11returnret
解法二：
考虑每一位的统计值，如果累加到3就归为0，则只会有0/1/2三种情况，所以将大小为32的int数组改为只用两个int即可。
第一个int的第i位为0/1代表第i位当前累加有0/1个 1 ，第二个int的第i位为1代表第i位当前累加有2。
当int1和int2中的第i位均为1时，我们将他们都清零。
例如：数组 [4 7 4 4](这里为了方便，我们取int的最后四位)
40100
one 0100
two 0 000
=====================
70111
one 0011
two 0 100
=====================
40100
one 0000
two 0 011
=====================
40100
one 0100
two 0 000
=====================
代码：
1defSingleNumber2_2(Array):2one =03two =04three =05foriinrange(0, len(Array)):6two |= (one &Array[i])7one ^=Array[i]8three = one &two9two -=three10one -=three11returnone
==========================================================
Problem 3：一个数组中有两个数字a、b只出现一次，其他数字都出现了两次。请找出这两个只出现一次的数字？
思路：若将数组中的所以数字进行异或，那么最终结果为 a ^ b
由于a != b，可以知道a ^ b != 0.即结果肯定有一位为1.
根据那一位，我们知道a，b的那一位肯定一个是0，一个是1.
我们找到为1的那一位i，根据i位为0/1将数组分成两组，即可将a, b分开。
因此，我们要解决的是两个Problem 1.
代码：
1defSingleNumber3(Array):2ret =03foriinrange(0,len(Array)):4ret ^=Array[i]5pos =06forjinrange(0,32):7if(ret>>j) & 1:8pos =j9
break10sub1,sub2 =split(Array,pos)11single1 =SingleNumber1(sub1)12single2 =SingleNumber1(sub2)13returnsingle1,single21415defsplit(Array, pos):16sub1 =[]17sub2 =[]18foriinrange(0,len(Array)):19if(Array[i]>>pos) & 1:20sub1.append(Array[i])21else:22sub2.append(Array[i])23returnsub1,sub2
1defSingleNumber3(Array):2ret =03foriinrange(0,len(Array)):4ret ^=Array[i]5pos =06forjinrange(0,32):7if(ret>>i) & 1:8pos =i9
break10sub1,sub2 =split(Array,pos)11single1 =SingleNumber1(sub1)12single2 =SingleNumber1(sub2)13returnsingle1,single21415defsplit(Array, pos):16sub1 =[]17sub2 =[]18foriinrange(0,len(Array)):19if(Array[i]>>pos) & 1:20sub1.append(Array[i])21else:22sub2.append(Array[i])23returnsub1,sub2
==========================================================
Problem 4：一个数组中有一个数字a只出现一次，其他数字都出现了K次。请找出这个只出现一次的数字？
考察知识点：位运算 and 分情况解决
① K % 2 == 0
基本思路类似于Problem 1
② K % 2 == 1
基本思路类似于Problem 2
代码：
1defSingleNumber4(Array, k):2ifk % 2 ==0:3ret =SingleNumber1(Array)4else:5ret =SingleNumber2_1(Array)6returnret
==========================================================
Problem 5：一个数组中有三个数字a、b、c只出现一次，其他数字都出现了两次。请找出这三个只出现一次的数字？
思路：此处转载自：http://zhedahht.blog.163.com/blog/static/25411174201283084246412/
如果我们把数组中所有数字都异或，那最终的结果（记为x）就是a、b、c三个数字的异或结果（x=a^b^c）。其他出现了两次的数字在异或运算中相互抵消了。
我们可以证明异或的结果x不可能是a、b、c三个互不相同的数字中的任何一个。
我们用反证法证明。假设x等于a、b、c中的某一个。比如x等于a，也就是a=a^b^c。因此b^c等于0，即b等于c。这与a、b、c是三个互不相同的三个数相矛盾。
由于x与a、b、c都各不相同，因此x^a、x^b、x^c都不等于0。
我们定义一个函数f(n)，它的结果是保留数字n的二进制表示中的最后一位1，而把其他所有位都变成0。比如十进制6表示成二进制是0110，
因此f(6)的结果为2（二进制为0010）。f(x^a)、f(x^b)、f(x^c)的结果均不等于0。
接着我们考虑f(x^a)^f(x^b)^f(x^c)的结果。由于对于非0的n，f(n)的结果的二进制表示中只有一个数位是1，因此f(x^a)^f(x^b)^f(x^c)的结果肯定不为0。
于是f(x^a)^f(x^b)^f(x^c)的结果的二进制中至少有一位是1。假设最后一位是1的位是第m位。那么x^a、x^b、x^c的结果中，有一个或者三个数字的第m位是1。
我们使用反正法证明不可能三个数字第m位都是1.
如果x^a、x^b、x^c的第m位都是1，那么a、b、c三个数字的第m位和x的第m位都相反，因此a、b、c三个数字的第m位相同。如果a、b、c三个数字的第m位都
是0，x=a^b^c结果的第m位是0。由于x和a两个数字的第m位都是0，x^a结果的第m位应该是0。同理可以证明x^b、x^c第m位都是0。这与我们的假设矛盾。
如果a、b、c三个数字的第m位都是1，x=a^b^c结果的第m位是1。由于x和a两个数字的第m位都是1，x^a结果的第m位应该是0。
同理可以证明x^b、x^c第m位都是0。这还是与我们的假设矛盾。
因此x^a、x^b、x^c三个数字中，只有一个数字的第m位是1。于是我们找到了能够区分a、b、c三个数字的标准。
=============================================================
这里我们需要注意上面只是在已知ａ，ｂ，ｃ的情况下的理论证明，具体编程则有些不一样：
我们先求得x = a ^ b ^ c
我们可以将x分别与数组中的元素再进行一次异或，得到一个新的数组，但是并没有改变数组的特性。
比如与数组中有两个相等的数字d
那么经过处理之后这两个数还是相等的，只不过结果为x ^ d
==============================================================
这样我们可以将数组分成两部分，这里假设a的m位为1。
则两个子数组分别为：sub1：包含a ==Problem 1
sub2：包含b, c ==Problem２
代码：
1defSingleNumber5(Array):2x =03foriinrange(0,len(Array)):4x ^=Array[i]5newArray =[]6forjinrange(0,len(Array)):7newArray.append(x^Array[j])8lastOneArrary =func(newArray)9ret =010foriinrange(0,len(lastOneArrary)):11ret ^=lastOneArrary[i]12pos =013forjinrange(0,32):14if(ret>>j) & 1:15pos =j16
break17sub1, sub2 =split(Array,pos)18print(sub1)19print(sub2)20iflen(sub1)%2:21single1 =SingleNumber1(sub1)22single2, single3 =SingleNumber3(sub2)23else:24single1 =SingleNumber1(sub2)25single2, single3 =SingleNumber3(sub1)26returnsingle1, single2, single327282930deffunc(Array):31newArray =[]32foriinrange(0,len(Array)):33pos =034forjinrange(0,32):35if(Array[i]>>j) & 1:36pos =j37
break38newArray.append(1<<pos)39returnnewArray