1.题目
一个数组，里面得数出现的次数是偶数次，只有一个数出现的次数是奇数次，找出那个出现奇数次的数
例如：
随意给一个数组 a[]={1, 2, 3, 3,2,1, 5}，其中出现基数次的数为5
分析：
- 大多数人看到此题，十有八九会用穷举法，遍历……
- 然而，如此题，最佳答案，用的是异或运算
2. 考点 ： 异或运算
2.1 异或算式
1^1=0
0^0=0
1^0=1
0^1=1
2.2 交换律和结合律
a ^ b = b ^ a
a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
2.3 提示
编程中，异或运算是在二进制上的异或运算
例如：
- 5的二进制是101
- 3的二进制是011
- 2的二进制是010
- 1的二进制是001
a[]={
1, 2, 3, 3,2,1, 5};
排开算算~：
- 1的二进制是001
- 2的二进制是010
- 3的二进制是011
- 3的二进制是011
- 2的二进制是010
- 1的二进制是001
- 5的二进制是101
计算结果：
1.先计算最右边第一位，有2个0和5个1，异或结果是：1
2.同理计算右边第二位，有3个0和4个1，异或结果是：0
3.同理计算右边第三位，有6个0和1个1，异或结果是：1
4.计算结果为：101，即十进制的5，计算正确！
3.编写代码
3.1 C语言实现
- 如下实现可见，只需要1次循环，就可以将数组中的奇数次数字，把它给找出来！
- 时间复杂度为Ο(n)
#include<stdio.h>
int main()
{
int a[]={
1,2,3,3,2,1,5};
int b[]={
1,1,2,2,4,4,9,8,7,7,8};
int i=0,j=0;
/* 先试试数组a，看看结果和2.3的提示一样么？ */
for(i=0;i<sizeof(a)/sizeof(int);i++)
{
j^=a[i];
}
printf("数字a的奇数次数字是:%d\n", j);
/* 下面再试试另一个数组b */
j=0;
for(i=0;i<sizeof(b)/sizeof(int);i++)
{
j^=b[i];
}
printf("数字b的奇数次数字是:%d\n", j);
return 0;
}
3.2 运行结果
szhou@notebook:~/works/learn/amazon-1$ gcc a1.c -o a1
szhou@notebook:~/works/learn/amazon-1$ ./a1
数字a的奇数次数字是:5
数字b的奇数次数字是:9
szhou@notebook:~/works/learn/amazon-1$
