美文网首页
LeetCode算法解题集:Single Number

LeetCode算法解题集:Single Number

作者: 海阔天空的博客 | 来源:发表于2021-11-10 06:59 被阅读0次

    题目:
    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

    相关文章

      网友评论

          本文标题:LeetCode算法解题集:Single Number

          本文链接:https://www.haomeiwen.com/subject/dcqgoltx.html