Given a non-empty 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?

Example 1:

1
2

Input: [2,2,1]
Output: 1

Example 2:

1
2

Input: [4,1,2,1,2]
Output: 4

O(1)time O(n)space

先将所有数字存入hash table，key是数字，value是数字的个数。

1
2
3
4
5
6
7

int (vector<int>& nums) {
    unordered_map<int, int> m;
    for (int i = 0; i<nums.size(); i++) 
        ++m[nums[i]]; 
    for (int i = 0; i<nums.size(); i++) 
        if (m[nums[i]] == 1) return nums[i]; 
    return 0;

Bit manipulation

1
2
3
4
5

int (vector<int>& nums) {
    int ret=0;
    for(auto num:nums) ret^=num; 
    return ret;
}