[LintCode] 82 Single Number 解题报告

Description
Given 2*n + 1 numbers, every numbers occurs twice except one, find it.


Example
Given [1,2,2,1,3,4,3], return 4


Challenge
One-pass, constant extra space.


思路
数学题。把每一个数看成二进制表示。我们知道任何一个数字A xor A == 0。那么如果这个数字出现过偶数次，我们只要过一遍xor就可以把它抵消掉（xor的结果是0）。我们还知道B xor 0 == B。
很显然，我们走一遍所有的数字，把它们全部xor。结果就是多出来的那个数字。
举个简单的例子：
((2^2)^(1^1)^(4^4)^(5)) => (0^0^0^5) => 5.


Code

public class Solution {
    /**
      *@param A : an integer array
      *return : a integer 
      */
    public int singleNumber(int[] A) {
        // Write your code here
        int result = 0;
        for (int i = 0; i < A.length; i++) {
            result ^= A[i];
        }
        return result;
    }
}