Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
class Solution {
public:
int singleNumber(vector<int>& nums) {
int w = sizeof(int)*8; //一个整数的字长
int *count = new int[w];
memset(count,0,sizeof(int)*w); //数组一定要初始化,否则会出现意外的值
int n = nums.size();
for(int i=0;i<w;i++)
{
for(int j=0;j<n;j++)
{
count[i] += (nums[j]>>i)&0x01;
}
count[i] = count[i]%3;
}
int result=0;
for(int i=0;i<w;i++)
{
result += (count[i]<<i);
}
return result;
}
};
网友评论