boj1377 位

2 of 3sSubmit: 311   Accepted:74Time Limit: 8000MS   Memory Limit: 1000KDescription
Given n numbers, n-1 of them appear exactly 3 times, one appears only twice.
Can you tell which number appeared only twice?


Input
Each case begins with a number n(0 < n < 10^6).
Followed with 3n-1 integers in range[- 2^31,2^31 - 1].


Output
For each case output the required number in a line.


Sample Input

3
-2 4 7 7 4 4 -2 -2
6
66 18 9 0 4 1 1 0 18 9 4 18 66 0 66 4 1


Sample Output

7
9


Hint
Huge input, scanf recommended.


Source
champ

此题大意是说，给定一数字n，输入3n-1个数，其中有n-1个数出现了3次，1个数只出现了2次，让找出那个出现2次的数。

看题目要求，时间限制很宽，但内存严格限制，故不可能用开大数组的方法暴力解，联想到以前做过的一道题，大意是2n-1个数，其中n-1个数出现2 次，1个数出现1次，找出那个孤独的数。这个题的做法是用异或，从0开始，将2n-1个数依次异或，最后的结果就是那个单独的数，因为n-1个重复的数异 或都得0了，最后异或的结果就是那个单独的数。

该题和此题十分类似，但是不能够直接异或而已，要用到位统计的思想。所有数字范围为2^-31~2^31-1,因此最多要用32位来表示，因此设定 一个数组check[32]来统计每一位上1出现的次数,3n-1个数的每一位都统计完后,对数组进行分析.因为n-1个数出现了3次,1个数出现了2 次,因此该数所在的对应位统计的结果一定不是3的倍数,以0为基数,或上1<

#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[])
{
    int n, i, j, stat[32], ret, num, loop;

    while (EOF != scanf("%d", &n))
    {
        memset(stat, 0, sizeof(stat));
        loop = 3 * n - 1;
        for (i=0 ; i<loop ; i++)
        {
            scanf("%d", &num);
            for (j=0 ; j<32 ; j++)
            {
                if ((1 << j) & num)
                    stat[j]++;
            }
        }
        ret = 0;
        for (i=0 ; i<32 ; i++)
        {
            if (stat[i] % 3)
                ret += (1 << i);
        }
        printf("%d\n", ret);
    }
}