给出 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,即落单的数。
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;
}
}