文章作者：姜南(Slyar) 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
09-12-05网络赛的一道题，用到了异或运算的几个性质。
Description
现在有n个数，只有一个数出现奇数次，把它找出来。
Input
首先一个T表示有T组数据。
每组数据一个n表示有(n<=100000)个数。
接下来n个数字a0,a1……an-1（ ai在int型范围内）。
Output
输出那个出现奇数次的数。
Sample Input
2
3
2 2 100000000
5
1 2 2 2 2
Sample Output
100000000
1
Slyar:暴力会超时，不说了。更简单的办法是用异或运算的几个性质:
1、A xor A = 0，也就是说异或同一个数偶数次，结果不变。
2、异或运算满足交换律。
这样我们只需要按顺序把所有的数依次异或一遍，剩下的就是唯一出现奇数次的那个数了。更复杂的一个问题是有2个数字出现奇数次，这样异或一遍会得到那2个数异或的结果，找出2个数二进制中不同的一位，然后把所有这n个数按照在那一位是0还是1分成两类，然后对每一类分别使用前一个问题的算法即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <stdio.h> #include <stdlib.h> int a[100001]; int main() { int i, t, n; int val; scanf("%d", &t); while(t--) { val = 0; scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &a[i]); } for (i = 0; i < n; i++) { val ^= a[i]; } printf("%d\n", val); } //system("pause"); return 0; } |
转载请注明：Slyar Home » 找出N个数字中唯一出现奇数次的数
