线性时间查找出现奇数次的元素

问题描述: 给定一个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;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容