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<int>& nums) {
map<int, int> m;
int n = nums.size();
for(int i = ; i < n; i ++)
{
if(m.find(nums[i]) == m.end())
m[nums[i]] = ;
else
m[nums[i]] ++;
}
for(map<int, int>::iterator it = m.begin(); it != m.end(); it ++)
{
if(it->second != )
return it->first;
}
}
};
解法二：先排序，再遍历找出孤异元素
class Solution
{
public:
int singleNumber(vector<int>& nums)
{
int n = nums.size();
sort(nums.begin(), nums.end());
//note that at least 4 elements in nums
if(nums[] != nums[])
return nums[];
if(nums[n-] != nums[n-])
return nums[n-];
for(int i = ; i < n-; i ++)
{
if(nums[i] != nums[i-] && nums[i] != nums[i+])
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<int>& nums) {
int ret = ;
int mask = ;
while(mask)
{
int countOne = ; //number of digit 1
for(int i = ; i < nums.size(); i ++)
{
if(nums[i] & mask)
countOne ++;
}
if(countOne % == )
ret |= mask;
mask <<= ;
}
return ret;
}
};