题意：
给你n个数字，已知只有一个数字出现了奇数次，其他数字都出现了偶数次，要求你找出这个特别的数字。
解题思路：
题目内存限制：1024K，所以不能简单地用数组存然后再处理。
为了节约内存，可以用STL里面的set,map等容器。
当容器里没有这个元素的时候，就插入这个元素，否则，删除这个元素。
最后，容器中肯定只剩下一个元素，便是我们所要的结果。
[cpp]
- #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]
- #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;
- }
[cpp]
- void swap(int &a,int &b)
- {
- a ^= b;
- b ^= a;
- a ^= b;
- }