算法面试题(python)——如何找出数组中出现一次的数

题目描述：

一个数组里，除了三个数是唯一出现的，其余的数都出现了偶数次，找出这三个数中任意一个。比如数组序列为[1,2,4,5,6,4,2]，只有1、5、6这三个数字是唯一出现的，数字2、4均出现了偶数次，只需要输出数字1、5、6中的任意一个就行。

分析：

题目得出的信息：

（1）数组中的元素一定为奇数个；

（2）由于只有三个数字均出现过一次，显然这三个数字不相同，因此，这三个数字对应的二进制也不可能完全相同。

解题思路：

因此可知：必定能找到二进制数中的某一个bit来区分这三个数（这一个bit的取值或者为0，或者为1），当通过这一个bit的值对数组进行分组的时候，这三个数一定是可以被分到两个子数组中去，。此时我们只需要重点关注哪个子数组中分配了这三个数的其中一个，就可以很容易得到这个数字了。当数组被划分成两个子数组时，这一个bit的值为1的数被分到一个子数组subArray1中，这一个bit的值为0的数被分到了另外一个子数组subArray0.

（1）如果subArray1中元素个数为奇数个，那么对subArray1中的所有数字进行异或操作；由于a^a=0，a^0=a,出现两次的数字通过异或操作得到结果为0，然后再与只出现一次的数字执行异或操作，得到的结果只出现一次的数字。

（2）如果subArray0中元素个数为奇数个，那么对subArray0中的所有数字进行异或操作得到的结果就是其中一个只出现一次的数字。

区分三个数字bit位及算法的实现思路：

32位平台为例，一个int类型的数字占用32位空间，从右往左使用每一位对数组进行分组，分组过程中，计算这个bit值为0的数字的异或的结果result0，出现次数count0；这个bit值为1的所有数字异或结果result1，出现次数为count1；

如果count0是奇数且result1 ！= 0 ，那么说明这三个数的其中一个数被分配到了这一个bit为0的子数组，因此，这个子数组中所有数字异或的值result0一定为出现的数字。（如果result1=0说明这一个bit不能用来区分这三个数字，此时这三个数字都被划分到子数组subArray0中，因此，result1！=0就可以确定这一个bit可以被用来划分这三个数字）

同理，如果count1是奇数且result0！=0，那么result1就是其中一个出现1次的数。

以[6,3,4,5,9,4,3]为例，出现1次的数字为6(110)、5(101)、9(1001)，从右往左第一位就可以区分这三个数字，用这个bit位可以把数字区分为两个子数组subArray0=（6，4，4）和subArray1=（3，5，9，3）。subArray1中所有元素异或的值不等于0，说明出现一次的数字一定在subArray1中出现了，而subArray0中的元素个数为奇数个，说明出现一次的数字其中只有一个被分配到subArray0中了，所以subArray0中所有的元素异或的结果就是这个出现1次的数字6，实现算法的python代码如下：

#判断数字n的二进制数从右往左的第i位是否为1
def isOne(n,i):
return (n&(1<<i)) == 1def findSingle(arr):
size = len(arr)
for i in range(32):
result0 = result1 = count0 = count1 = 0
for j in range(size):
if isOne(arr[j],i):
result1 ^= arr[i]
count1 += 1
else:
result0 ^= arr[j]
count0 += 1
"""
bit值为1的子数组元素个数为奇数时，且出现1次的的数字被分配到bit值为0的子数组，
说明只有一个出现的数字被分配到bit的值为1的子数组中，异或记过就是这个出现一次的数字
"""
if count1 % 2 == 1 and result0 != 0:
return result1
#只有一个出现一次的数字被分配到bit值为0的子数组中
if count0 % 2 == 1 and result1 != 0:
return result0
return -1