136.只出现一次的数字.md

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

eg:

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

思路描述：这个思路应该还是比较直观的，可以用unordered_map去存每个元素数目，然后遍历一下取出来个数为1的元素。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> count;
        int result = 0;
        for(int i = 0; i < nums.size(); i ++){
            count[nums[i]] ++;
        }
        unordered_map<int, int>::iterator it = count.begin();
        for(; it != count.end(); it ++){
            if(it->second == 1) result = it->first;
        }
        return result;
    }
};

用set元素的不重复性以及

2(a+b+c)-(2a+2b+c)=c

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        set<int> count;
        int result = 0, sum1 = 0, sum2 = 0;
        for(int i = 0; i < nums.size(); i ++){
            count.insert(nums[i]);
            sum2 += nums[i];
        }
        for(set<int>::iterator it=count.begin(); it!=count.end(); it++){
            sum1 += *it;
        }
        return 2*sum1 - sum2;
    }
};

其实这道题不单出是找只出现一次的元素，还有一个很重要的点，其余每个元素均出现两次，那么使用数学方法去求解一下，我们知道a^a=0， a ^ a ^ b=b

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