2019-11-13 只出现一次的数字

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

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

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

示例 2:

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

C++1

使用C++ STL中的set，先循环遍历将数组中的数据存在set<int,int>中，键为每个数字，值为出现的次数。第二次循环找出出现一次的那个数，返回。虽然题中说一定有一个元素只出现一次，但是最后还必须再写一个return，否则编译器会报错。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        map<int, int> m;
        for(int i:nums){
            map<int, int>::iterator iter;
            iter = m.find(i);
            int num;
            if(iter != m.end()){
                num = iter->second;
                m[i] = num+1;
            }else{
                m.insert(pair<int, int>(i, 1));
            }
        }
        map<int,int>::iterator _iter = m.begin();
        for(;_iter !=m.end();_iter++)
        {
            if(_iter->second==1){
                return _iter->first;
            }
        }
        return nums[0];
    }
};