LeetCode算法解题集：Single Number

题目：
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?

思路：
建立一个map去存储已经循环过的数字，每次循环前先判断该值是否存在于map中，如果map内没有则添加进去，如果存在则清空该记录，最后循环完后，map里只有一条记录为最终该结果。算法复杂度：O(n)

代码：

class Solution {
public:

int singleNumber(vector<int>& nums) {
    map<int, int> vaule_map;
    for( unsigned int i = 0; i < nums.size(); i++ )
    {
        map<int, int>::iterator iIter = vaule_map.find(nums[i]);
        if( iIter == vaule_map.end() )
        {
            //empty
            vaule_map[nums[i]] = 1;
        }
        else
        {
            //find it and erase it
            vaule_map.erase(iIter);
        }
    }
    if( vaule_map.size() != 1 )
    {
        return -1;
    }
     
    map<int, int>::iterator iBegin = vaule_map.begin();
     
    return iBegin->first;
}

};
总结：
1、在网上看到其他解题思路，虽然可以节省内存，但着实没看下去。。
2、第一次提交一次通过！好开心。