不知道什么时候能用到这个算法,权当练习,其实也是应用数学基础知识的算法。
/**********************************************************************************************************************
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; }