转载自：http://blog.csdn.net/dgq8211/article/details/7455722
题目链接：Click here~~
题意：
给你n个数字，已知只有一个数字出现了奇数次，其他数字都出现了偶数次，要求你找出这个特别的数字。
解题思路：
题目内存限制：1024K，所以不能简单地用数组存然后再处理。
为了节约内存，可以用STL里面的set,map等容器。
当容器里没有这个元素的时候，就插入这个元素，否则，删除这个元素。
最后，容器中肯定只剩下一个元素，便是我们所要的结果。
[cpp] view plain copy #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。
所以可以通过每次异或运算，最后剩下的值就是出现奇数次的那个数字。
[cpp] view plain copy #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的值的交换。
[cpp] view plain copy void swap(int &a,int &b) { a ^= b; b ^= a; a ^= b; }
