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?

注意：多关键字的multimap不能使用下标操作。

C++代码如下：

#include<iostream>
#include<map>
using namespace std;

class Solution
{
public:
    int singleNumber(int A[],int n)
    {
        multimap<int,int> mp;
        int i;
        for(i=0;i<n;i++)
        {
            mp.insert({A[i],i});
        }
        auto map_it=mp.begin();
        while(map_it!=mp.end())
        {
            auto tmp=map_it;
            tmp++;
            if((tmp)==mp.end())
                return (map_it)->first;
            if(map_it->first!=(tmp)->first)
                break;
            map_it++;
            map_it++;
        }
        return map_it->first;
    }
};

int main()
{
    Solution s;
    int arr[]={2,4,2,4,5};
    cout<<s.singleNumber(arr,5)<<endl;
}

第二遍刷：

    int singleNumber(int A[],int n)
    {
        multiset<int> st;
        int i;
        for(i=0;i<n;i++)
            st.insert(A[i]);
        for(i=0;i<n;i++)
            if(st.count(A[i])!=2)
                break;
        return A[i];
    }