单个数字

问题

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?

思路

由于加上了时间复杂度必须是O(n)，并且空间复杂度为O(1)使得不能用排序方法，也不能使用map数据结构

网上大神的思路
因为A XOR A = 0，且XOR运算是可交换的，于是，对于实例{2,1,4,5,2,4,1}就会有这样的结果：
(2^1^4^5^2^4^1) => ((2^2)^(1^1)^(4^4)^(5)) => (0^0^0^5) => 5

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            res ^= nums[i];
        }
        return res;
    }
};

C++小知识

异或操作满足交换律和结合律
map的insert，插入一个值，或者一个数组时，返回是否插入成功。

pair<iterator,bool> insert ( const value_type& val );

template <class P>
    pair<iterator,bool> insert ( P&& val );

In versions (1) and (2), the function returns a pair object whose first element is an iterator pointing either to the newly inserted element in the container or to the element whose key is equivalent, and a bool value indicating whether the element was successfully inserted or not.