136.只出现一次的数字

思路

这题要用到异或运算的性质。亦或运算满足结合律和交换律，这意味着如果对一系列数字连续使用异或运算，其顺序并不影响运算的结果，这就非常符合这题的输入条件。

而且，异或运算满足0与任何数异或得该数本身，任何数与该数本身异或得0。这意味着如果一个数出现了偶数次，我们就可以用交换律使其结果得0。这样，运算的最终结果就是那个只出现了一次的数字。

线性时间，常量空间

位运算也是一个选择， 因为位运算把信息存储在一个int里面，这样就达到了常量空间。

算法

class Solution {
    public int singleNumber(int[] nums) {
        int n = nums.length;
        int xor = 0;
        for (int i = 0; i < n; i++) {
            xor ^= nums[i];
        }
        return xor;
    }
}