描述 Description

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?

[Single Number]

分析 Analysis

方法1

使用hashmap，key记录每个数，value初始化0，碰到一个就置1，再碰到一个删除。剩下的最后一个就是了。

算法时间复杂度O(n)，空间复杂度O(n)。

或者使用bitmap记录一个int数的bit位，每来一个int数，对应位取反，有1就清0，有0就置1，最后留下的就是那个独立存在的数。（其实就是方法2）

方法2

使用位操作，任意两个相同的数做异或运算（不进位加法），结果为 0，也即 A ^ A = 0 ，而 A ^ 0 = A 。

所以可以对整个数组遍历，累积异或，只要某个数存在两个相同，总会清除掉其对应的bit位。最后得到的结果就是独立存在的数。

Note: 异或，不仅能处理两次的情况，只要出现偶数次，都可以清零，也就是如果其它数都存在2n次，异或都可以将它们清除掉。

算法时间复杂度O(n)，不需要空间。

代码 Code

// Single Number
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int x = 0;
        for (int i : nums)
            x ^= i;
        return x;
    }
};