题目链接:Click here~~

题意:

给你n个数字,已知只有一个数字出现了奇数次,其他数字都出现了偶数次,要求你找出这个特别的数字。

解题思路:

题目内存限制:1024K,所以不能简单地用数组存然后再处理。

为了节约内存,可以用STL里面的set,map等容器。

当容器里没有这个元素的时候,就插入这个元素,否则,删除这个元素。

最后,容器中肯定只剩下一个元素,便是我们所要的结果。

#include <set>
#include <stdio.h>
using namespace std;
int main()
{
    int n,x;
    set <int> S;
    while(scanf("%d",&n),n)
    {
        while(n--)
        {
            scanf("%d",&x);
            if(S.find(x) == S.end())    //没找到,插入
                S.insert(x);
            else                        //找到了,删除
                S.erase(x);
        }
        printf("%d\n",*S.begin());
        S.clear();
    }
    return 0;
}

其实,这题还有个更好的方法————位异或。

我们先了解一下位异或的运算法则吧:

1、a^b = b^a。

2、(a^b)^c = a^(b^c)。

3、a^b^a = b。

对于一个任意一个数n,它有几个特殊的性质:

1、0^n = n。

2、n^n = 0。

所以可以通过每次异或运算,最后剩下的值就是出现奇数次的那个数字。

#include <stdio.h>
int main()
{
    int n,x,ans;
    while(scanf("%d",&n),n)
    {
        ans = 0;
        while(n--)
        {
            scanf("%d",&x);
            ans ^= x;
        }
        printf("%d\n",ans);
    }
    return 0;
}
PS:话说通过位运算的这些性质,可以通过不借用中间变量实现a,b的值的交换。

void swap(int &a,int &b)
{
    a ^= b;
    b ^= a;
    a ^= b;
}



Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐