单独的数字

题目：

给定一个数组，除了一个数出现1次之外，其余数都出现3次。找出出现一次的数。
如：{1, 2, 1, 2, 1, 2, 7}, 找出7.
格式：第一行输入一个数n，代表数组的长度，接下来一行输入数组A[n],(输入的数组必须满足问题描述的要求),最后输出只出现一次的数。
要求：你的算法只能是线性时间的复杂度，并且不能使用额外的空间哦～

思路：

首先这题很容易联想到另外一题，也是找出单独的数，不同的是，另外一题中其他数都是出现2次，所以使用异或运算后，对于二进制每一位，相同的数就被消除了，得到了单独的数字。但是，这题中其他数字是出现3次的。不过我们还是可以从前面的解法得到启发，使用二进制的位运算，既然其他每次数都出现3次，那么如果针对每一位求和并对3取余，那么那些出现3次的数字在这一位的和对3取余后肯定是0，其实就是单独的那个数在这一位上的结果。所以，针对32位的整数，我们只要求出二进制的每一位的和对3取余，就是单独的数的二进制，再转化成10进制，就是我们需要的答案。

文／破东风CAFEBABY（简书作者）
原文链接：http://www.jianshu.com/p/8c454ade848e
著作权归作者所有，转载请联系作者获得授权，并标注“简书作者”。