single number

ddatsh

dev #算法

在一个整型数组中，所有的数字都出现了两次，只有一个数是例外，找出这个数

还要求要在不使用额外空间的情况下找到解、要求的线性复杂度

使用二分查找倒是不会用到额外空间，可是时间复杂度为O(nlogn),又不符合线性复杂度

用异或运算的性质：

a xor a = 0
0 xor a = a
a xor b = b xor a

把数组中所有的数异或起来，得到的结果就是仅出现了一次的数

int[] n = new int[]{1, 1, 2, 2, 3, 4, 4, 5, 5};
int ans = 0;
for (int i = 0; i < n.length; ++i) {
	ans ^= n[i];
}
System.out.println(ans);