Single Number II

Given an array of integers, every element appears threetimes 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记录次数

class Solution {public:    int singleNumber(vector
     
      & nums) {        map
      
        m;        int n = nums.size();        for(int i = 0; i < n; i ++)        {            if(m.find(nums[i]) == m.end())                m[nums[i]] = 1;            else                m[nums[i]] ++;        }        for(map
       
        ::iterator it = m.begin(); it != m.end(); it ++)        {            if(it->second != 3)                return it->first;        }    }};
       
      
     

 

解法二：先排序，再遍历找出孤异元素

class Solution {public:    int singleNumber(vector
     
      & nums)     {        int n = nums.size();        sort(nums.begin(), nums.end());        //note that at least 4 elements in nums        if(nums[0] != nums[1])            return nums[0];        if(nums[n-1] != nums[n-2])            return nums[n-1];        for(int i = 1; i < n-1; i ++)        {            if(nums[i] != nums[i-1] && nums[i] != nums[i+1])                return nums[i];        }    }};
     

 

解法三：位操作。不管非孤异元素重复多少次，这是通用做法。

对于右数第i位，如果孤异元素该位为0，则该位为1的元素总数为3的整数倍。

如果孤异元素该位为1，则该位为1的元素总数不为3的整数倍（也就是余1）。

换句话说，如果第i位为1的元素总数不为3的整数倍，则孤异数的第i位为1，否则为0.

（如果非孤异元素重复n次，则判断是否为n的整数倍）

class Solution {public:    int singleNumber(vector
     
      & nums) {        int ret = 0;        int mask = 1;        while(mask)        {            int countOne = 0;   //number of digit 1            for(int i = 0; i < nums.size(); i ++)            {                if(nums[i] & mask)                    countOne ++;            }            if(countOne % 3 == 1)                ret |= mask;            mask <<= 1;        }        return ret;    }};