LintCode | 82. 落单的数

题目

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

思路

对 0 和每个数字进行异或，相同的数字异或两次相当于没有进行操作，那么对每个数字异或完，结果就是落单的数。

代码

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