你可能不会做的算法题--单独的数字

今天看到一个算法题，感觉应该很简单就能搞定，但是想了很久还是没想到，囧。最后还是网上查了别人的解法，跟大家分享一下：

题目：

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

思路：

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

示意图：

{1, 2, 1, 2, 1, 2, 7}, 找出7的过程

代码：

#include<stdio.h>
int main(){
    int sum[32], n, a;
    for(int i=0; i<32; i++){
        sum[i] = 0;
    }
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d", &a);
        for(int j=0; j<32; j++){
            sum[j]+=a>>j&1;
            sum[j]%=3;
        }
    }
    int ans = 0;
    for(int i=0; i<32; i++){
        ans += sum[i]<<i;
    }
    printf("%d\n", ans);
}