Problem 1：一个数组中有一个数字a只出现一次，其他数字都出现了两次。请找出这个只出现一次的数字？
考察知识点：异或运算
思路：比如数字 b^b = 0
a^0 = a
因此，可以将数组中的所有数字进行异或，而最终异或的结果即为所求只出现一次的数字a.
代码：
def SingleNumber1(Array):
ret = 0
for i in Array:
ret ^= i
return ret
==========================================================
Problem 2：一个数组中有一个数字a只出现一次，其他数字都出现了三次。请找出这个只出现一次的数字？
考察知识点：位运算
解法一：
考虑用统计的思路来解这道题，如果一个数出现了三次就消掉，int的32个位都是由0/1组成的，所以将所有数的对应位加起来，
再将各位的统计和对3取模，最终剩下的结果就是要找出的数。
例如：数组 [4 7 4 4](这里为了方便，我们取int的最后四位)
0 1 0 0
0 1 1 1
0 1 0 0
0 1 0 0
Sum 0 4 1 1
Sum%3 0 1 1 1
最后Sum%3得到的结果0111即7，就是我们所要求的Single Number
代码：
def SingleNumber2_1(Array):
ret = 0
for i in range(0,32):
c = 0
d = 1 << i
for j in range(0, len(Array)):
if Array[j] & d:
c += 1
if c % 3:
ret |= d;
return ret
解法二：
考虑每一位的统计值，如果累加到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的最后四位)
4 0 1 0 0
one 0 1 0 0
two 0 0 0 0
=====================
0 1 1 1
one 0 0 1 1
two 0 1 0 0
=====================
0 1 0 0
one 0 0 0 0
two 0 0 1 1
=====================
4 0 1 0 0
one 0 1 0 0
two 0 0 0 0
=====================
代码：
def SingleNumber2_2(Array):
one = 0
two = 0
three = 0
for i in range(0, len(Array)):
two |= (one & Array[i])
one ^= Array[i]
three = one & two
two -= three
one -= three
return one
==========================================================
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.
代码：
def SingleNumber3(Array):
ret = 0
for i in range(0,len(Array)):
ret ^= Array[i]
pos = 0
for j in range(0,32):
if (ret>>j) & 1:
pos = j
break
sub1,sub2 = split(Array,pos)
single1 = SingleNumber1(sub1)
single2 = SingleNumber1(sub2)
return single1,single2 def split(Array, pos):
sub1 = []
sub2 = []
for i in range(0,len(Array)):
if (Array[i]>>pos) & 1:
sub1.append(Array[i])
else:
sub2.append(Array[i])
return sub1,sub2
def SingleNumber3(Array):
ret = 0
for i in range(0,len(Array)):
ret ^= Array[i]
pos = 0
for j in range(0,32):
if (ret>>i) & 1:
pos = i
break
sub1,sub2 = split(Array,pos)
single1 = SingleNumber1(sub1)
single2 = SingleNumber1(sub2)
return single1,single2 def split(Array, pos):
sub1 = []
sub2 = []
for i in range(0,len(Array)):
if (Array[i]>>pos) & 1:
sub1.append(Array[i])
else:
sub2.append(Array[i])
return sub1,sub2
==========================================================
Problem 4：一个数组中有一个数字a只出现一次，其他数字都出现了K次。请找出这个只出现一次的数字？
考察知识点：位运算 and 分情况解决
① K % 2 == 0
基本思路类似于Problem 1
② K % 2 == 1
基本思路类似于Problem 2
代码：
def SingleNumber4(Array, k):
if k % 2 == 0:
ret = SingleNumber1(Array)
else:
ret = SingleNumber2_1(Array)
return ret
==========================================================
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２
代码：
def SingleNumber5(Array):
x = 0
for i in range(0,len(Array)):
x ^= Array[i]
newArray = []
for j in range(0,len(Array)):
newArray.append(x^Array[j])
lastOneArrary = func(newArray)
ret = 0
for i in range(0,len(lastOneArrary)):
ret ^= lastOneArrary[i]
pos = 0
for j in range(0,32):
if (ret>>j) & 1:
pos = j
break
sub1, sub2 = split(Array,pos)
print(sub1)
print(sub2)
if len(sub1)%2:
single1 = SingleNumber1(sub1)
single2, single3 = SingleNumber3(sub2)
else:
single1 = SingleNumber1(sub2)
single2, single3 = SingleNumber3(sub1)
return single1, single2, single3 def func(Array):
newArray = []
for i in range(0,len(Array)):
pos = 0
for j in range(0,32):
if (Array[i]>>j) & 1:
pos = j
break
newArray.append(1<<pos)
return newArray