找出数组中出现仅一次的数字

有一个元素类型是整数的数组,数组中有一个数字仅仅出现了一次,其它都出现了两次,现在请把这个仅仅出现一个找出来。

分析:

1.1  首先想到的是排序,这样的时间复杂度是O(n*logn) + O(n),这样的速度的确不咋地;

1.2  最好的方法不是自己想出的,在网上找到的,是利用位运算的性质,两个相同的数字异或运算的结果是0,0和任何整数的异或运算是其本身,这两点足以,所以我们只需要遍历一边整个数组即可,时间复杂度是O(n)。

2 程序实现

#include <iostream>
using namespace std;
void main()
{
	int arr[] = {1,5,4,7,9,3,4,5,1,9,7};
	int nLength = sizeof(arr)/sizeof(arr[0]);
	int sum=0;
	for(int i=0;i<nLength;i++)
	{
		sum = sum ^ arr[i];
	}
	cout<<sum;
}

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。