L1-落单的数

Posted on | In |

描述
给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。
样例
给出 [1,2,2,1,3,4,3]，返回 4

挑战
一次遍历，常数级的额外空间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    /**
     * @param A: An integer array
     * @return: An integer
     */
    public int singleNumber(int[] A) {
        // write your code here
         if (null == A || A.length == 0) {
            return 0;
        }
        int res=0;
        for(int i=0;i<A.length;i++)
        {
            res^=A[i];
        }
        return res;
    }
}

将数组的数全部做异或，最后得到的数就是要找的数，因为和一个数做两次异或不会改变。