现在的位置: 首页 > 综合 > 正文

找出数组中出现奇数次的元素

2018年02月21日 ⁄ 综合 ⁄ 共 556字 ⁄ 字号 评论关闭

不知道什么时候能用到这个算法,权当练习,其实也是应用数学基础知识的算法。

 

/**********************************************************************************************************************
2.找出数组中出现奇数次的元素
问题描述:现在有一个整数数组arr,其中的元素只有一个元素出现奇数次,请找出这个元素。
解决方案:对于任意一个数k,有k^k = 0,k^0 = k,所以将arr中所有元素进行异或,那么出现次数为偶数的元素异或后都变成了0,
出现次数为奇数的元素异或后得到元素本身。下面写代码就很容易了~~时间复杂度是O(n)。
*************************************************************************************************************************/

 

int getoddelements(int arr[], int length)
{
	int elements = 0;
	for(int i=0; i<length; i++)
	{
		elements ^= arr[i];
	}
	return elements;
}

 

抱歉!评论已关闭.