题目:
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
网友评论