Kotlin程序员面试：1次出现数搜索

【出自XM笔试题】

难度系数：★★★★☆ 被考察系数：★★★☆☆

题目描述：

一个数组里，除了三个数是唯一出现的，其余的数都出现偶数次，找出这三个数中的任意一个。比如数组序列为{1，2，4，5，6，4，2}，只有1，5，6这三个数字是唯一出现的，数字2与4均出现了偶数次（2次），只需要输出数字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中所有元素进行异或操作得到的结果就是其中一个只出现一次的数字。(www.xing528.com)

为了实现上面的思路，必须先找到能区分这三个数字的位，根据以上的分析给出本算法的实现思路：

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

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

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

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

程序的运行结果如下：

6

算法性能分析：

这种方法使用了两层循环，总共循环执行的次数为32*N（N为数组的长度），因此，算法的时间复杂度为O（N）。