落单的数

题意

给出 2*n + 1 个的数字,除其中一个数字之外其他每个数字均出现两次,找到这个数字。

样例

给出[1,2,2,1,3,4,3],返回 4

思路

在位运算中,异或(^)是将该数的二进制每一位进行异或运算,当前位的两个二进制表示不同则为 1 ,相同则为 0。

根据此特性,可以得出结论:两个相同的数进行异或运算的结果为 0。

即:5 ^ 5 = 0,那么 5 ^ 5 ^ 6 的结果就是 6,这样就符合本题的要求了,6 就是那个 2n + 1 中的 1,即落单的数。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
/**
*@param A : an integer array
*return : a integer
*/
public int singleNumber(int[] A) {
int r = 0;
for (int i = 0; i < A.length; i++) {
r ^= A[i];
}

return r;
}
}

原题地址

LintCode:落单的数