[map哈希异或] 136137260 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

 

方法一：直接异或全部。

class Solution { public:     int singleNumber(vector<int>& nums) {         int sum,i;         int len=nums.size();                  if(len==1)         {             return nums[0];         }                  sum=nums[0];         for(i=1;i<len;i++)         {             sum =sum ^ nums[i];         }         return sum;     } };

 

方法一更偏向于数学，对137题就不适用了，可以用map实现一个哈希（map内部红黑树需要了解）：

class Solution { public:     int singleNumber(vector<int>& nums) {         map<int,int> hash;                  int len,i;         len=nums.size();

        for(i=0;i<len;i++)         {             hash[nums[i]]++;         }                  map<int,int>::iterator it;

        it = hash.begin();

        while(it != hash.end())         {             if(it->second==1)             {                 return it->first;             }             it ++;                  }         return 0;     } };

 

同理260也可以用上述方法：

class Solution { public:     vector<int> singleNumber(vector<int>& nums) {         int len,i;         vector<int> a;         len=nums.size();                  map<int,int> hash;         map<int,int>::iterator it;                                    for(i=0;i<len;i++)         {             hash[nums[i]]++;         }                  it=hash.begin();         while( it!=hash.end() )         {             if(it->second==1)             {                 a.push_back(it->first);                              if(a.size()==2)                 {                     return a;                 }             }             it++;         }                  return a;     } };