问题描述: 给定一个n元素数组,只有一个元素出现奇数次。找出这个元素。
很容易想到的一个思路是空间换时间,建一个hash表记录每个元素出现的次数。最后找到出现奇数次的元素。
另一个思路利用位运算。对于任一个数k,k^k = 0, k^0 = k。所以对所有元素进行异或操作,那么个数为偶数的元素最后都变成了0,只留下个数为奇数的那个元素。
int findEleOddCount(int a[], int len)
{
int r=a[0];
int i;
for(i=1; i< len; i++)
r^=a[i];
return r;
}