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、第一次提交一次通过！好开心。

本文摘录于海阔天空的博客，作者: zjg555543，发布时间: 2015-07-27