序列中只有一个数出现了一次，其他均出现了两次，找出只出现过一次的这个数

例如：{10,9,8,7,6,6,7,8,9,10,5}

其中只有5出现了一次，其他的数均出现了两次，请找出这个数：5。

首先出现在我们脑海中的是最基本的方法：已知只有一个数出现过一次，那么只要嵌套两次循环就能找出只出现过一次的那个数，将他返回。

代码如下：

	public static Integer findOnlyNum(int[] array){
		
		for(int i = 0 ;i<array.length;i++){
			int j = 0;
			for(;j<=array.length;j++){
				if(i==j){
					continue;
				}
				if(j==array.length){
					break;
				}
				if(array[i]==array[j]){
					break;
				}
			}
			if(j==array.length){
				return array[i];
			}
		}
		return null;
	}

这个方法在时间复杂度上属于T(n^2),那么有没有更好的方法能够实现上述的功能呢？

在计算机原理中我们接触到一个位操作符：^

相同的结果会得到全0；和全0异或，结果不变；和全1异或，结果会得到自己的取反。

我们需要证明的是a^b^a^b=(a^a)^(b^b)，这一点参照计算机原理。

那么我们的代码就可以简化成：

	public static Integer findOnlyNum1(int[] array){
		int result = 0;
		for(int i = 0 ;i<array.length;i++){
			result^=array[i];
		}
		return result;
	}

序列中只有一个数出现了一次，其他均出现了两次，找出只出现过一次的这个数,布布扣,bubuko.com

序列中只有一个数出现了一次，其他均出现了两次，找出只出现过一次的这个数

原文：http://blog.csdn.net/cxming007/article/details/23738643