【解题报告】lintcode82落单的数

题意

数组里所有数都出现了两次，但是其中有一个只出现了一次，找出它 时间复杂度O(n)

解答

使用位运算，异或运算 由于其结合律 结合律：A^(B^C)=(A^B)^C 且如果两个数字相同，异或结果为0，0与仍和数字的异或为这个数字本身 我们把所有数字异或起来，就是我们要找的结果了

代码

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