单独的数字

给定一个数组,除了一个数出现1次之外,其余数都出现3次。找出出现一次的数。

如:{1, 2, 1, 2, 1, 2, 7}, 找出7.

格式:

第一行输入一个数n,代表数组的长度,接下来一行输入数组A[n],(输入的数组必须满足问题描述的要求),最后输出只出现一次的数。

分析:

涉及到位运算,用一个长度为32的数组保存整数的每一位出现的次数,最终次数能被3整除的表示该位为0,否则该位为1。

代码

#include <iostream>
#include <cstdio>

#define MaxN = 1000

using namespace std;

int main()
{
    int cnt[35] = {0};  //little-endian
    int n = 0;
    int temp = 0;
    int result = 0;
    scanf("%d", &n);
    for(int i=0; i<n; ++i){
        scanf("%d", &temp);
        for (int i=0; i<32; ++i){
            cnt[i] += (0 == (temp & (1 << i))) ? 0 : 1;
        }
    }
    for(int i=0; i<32; ++i){
        //printf("%d ", cnt[i]);
        result += (cnt[i] % 3) ? (1 << i) : 0;
    }
    printf("%d\n", result);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注