4
1 1 1 3
10
1 2 3 1 2 3 1 2 3 4

3
4

题目的大意就是给你3n+1个数，其他都是三个三个的出现，找出那个唯一的数。

这个题目很容易想到直接排序然后寻找唯一的这个数。复杂度为O(n*logn)。由于n为10^5。n*logn大概在2*10^6

便尝试了下：

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define maxn 100005
using namespace std;

long long a[maxn];

int cmp(long long p1,long long p2)
{
    if(p1<p2) return 1;
    return 0;
}

int main()
{
    int n,i;
    while(cin>>n)
    {
        for(i=0; i<n; i++)
            scanf("%lld",&a[i]);

        sort(a,a+n,cmp);
        if(n==1||a[0]!=a[1])
        {
            printf("%lld\n",a[0]);
            continue;
        }
        if(n>1&&a[n-1]!=a[n-2])
        {
            printf("%lld\n",a[n-1]);
            continue;
        }

        int cnt=1;
        for(i=1; i<n; i++)
        {
            if(a[i]==a[i-1])
                cnt++;
            else
            {
                if(cnt==1)
                {
                    printf("%lld\n",a[i-1]);
                    break;
                }
                cnt=1;
            }
        }
    }
}

于是在网上找大牛的思路：

最初看到下面的位运算的代码时，我也是拒绝的。。这样也可以。

不过细想了下。

one:              表示只出现过一次的数

accumulation:表示出现过两次的数

t:                  表示出现过三次的数，（取反之后可以用来删掉出现三次的数）

PS：这里说的出现次数都是针对每一位出现的次数。

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define maxn 100005
using namespace std;

long long a[maxn];

int main()
{
    int n,i;
    while(cin>>n)
    {
        for(i=0; i<n; i++)
            scanf("%lld",&a[i]);

        long long one = 0;   // 出现一次的标志位
        long long accumulation = 0;   // 积累标志位
        for (int i=0; i<n; i++)
        {
            accumulation |= a[i] & one;
            // 只要第二次或以上出现，就为1
            one ^= a[i];
            // 出现奇数次保留，偶数次抛弃
            long long t = one & accumulation;
            // 第三次的时候one和accumulation都保留了该位的值
            one &= ~t;
            // 清零出现三次的该位的值
            accumulation &= ~t;
        }

        printf("%lld\n",one);
    }
}

/*
4
1 1 1 3
10
1 2 3 1 2 3 1 2 3 4
*/