Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution1:  XOR
Run time complexity is O(n), constant space

public class Solution {
    public int singleNumber(int[] A) {
        int result = A[0];
        for(int i = 1; i < A.length; i++) {
            result = result ^ A[i];
        }
        return result;
    }
}

// 异或运算：a ^ a = 0, a ^ b ^ a = b

Solution2: bit operation

统计整数的每一位来得到出现次数。如果每个元素重复出现二次，那么每一位出现1的次数也会是2的倍数。统计完成后对每一位进行取余2，那么结果中就只剩下那个出现一次的元素。

只需要对数组进行一次线性扫描，统计完之后每一位进行取余2并且将位数字赋给结果整数。

Run time complexity is O(n), space complexity is O(32) = O(1), constant space.

public class Solution {
    public int singleNumber(int[] A) {
        if(A == null || A.length == 0) {
            return 0;
        }
        
        int[] digits = new int[32];
        for(int i = 0; i < 32; i++) {
            for(int j = 0; j < A.length; j++) {
                digits[i] += (A[j] >> i) & 1;
            }
        }
        
        int res = 0;
        for(int i = 0; i < 32; i++) {
            res += (digits[i] % 2) << i;
        }
        return res;
    }
}