题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

要求算法具有线性时间复杂度，且不使用额外空间实现。

链接

解题方法

位运算

使用异或运算⊕，异或运算的性质：

1. 任何数和0做异或运算，结果仍然是原来的数，即a⊕0=a。
2. 任何数与其自身做异或运算，结果是0，即a⊕a=a⊕a=0。
3. 异或运算满足交换律和结合律，即a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

Java写法：

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }
}

JavaScript写法：

var singleNumber = function(nums) {
    let single = 0;
    for(let num of nums) {
        single ^= num
    }
    return single;
};

时间复杂度为O(n)，空间复杂度为O(1)

拓展

空间复杂度与时间复杂度不要求时

使用集合存储数字

遍历数组中的每个数字，如果集合中没有该数字，则将该数字加入集合，如果集合中已经有该数字，则将该数字从集合中删除，最后剩下的数字就是只出现一次的数字。

var singleNumber = function(nums) {
    let numberSet = new Set()
    for(let num of nums) {
        if(numberSet.has(num)) {
            numberSet.delete(num)
        } else {
            numberSet.add(num)
        }
    }
    let myArray = Array.from(numberSet);
    return myArray[0]
};

哈希表

使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字。当数字出现次数不一定为2次时也可使用。

位运算符

实在是想不到使用异或运算解决这个问题，复习一下其他的位运算符。MDN

含义	运算符	特点
左移	<<	该操作符会将第一个操作数向左移动指定的位数。向左被移出的位被丢弃，右侧用 0 补充。
有符号右移	>>	该操作符会将第一个操作数向右移动指定的位数。向右被移出的位被丢弃，拷贝最左侧的位以填充左侧。由于新的最左侧的位总是和以前相同，符号位没有被改变。所以被称作“符号传播”。
无符号右移	>>>	该操作符会将第一个操作数向右移动指定的位数。向右被移出的位被丢弃，左侧用0填充。因为符号位变成了 0，所以结果总是非负的。（译注：即便右移 0 个比特，结果也是非负的。）
按位或	|	有1为1，全0为0
按位与	&	全1为1，有0为0
按位非	~	取反
按位异或	^	相同为0，不同为1