19
06/2015
[LeetCode] Single Number II
Single Number II
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
解题思路：
与Single Number不同，这里不能再用异或操作来做了。可以为每个位上1的数目计数。然后将该计数%3，剩下的1肯定是单独的数字贡献的。
class Solution {
public:
int singleNumber(vector<int>& nums) {
vector<int> bitNumCount(32, 0);
int len = nums.size();
for(int i=0; i<len; i++){
int num = nums[i];
for(int j = 0; j<32 && num!=0; j++){
if(num & 0x1 == 1){
bitNumCount[j]++;
}
num = num>>1;
}
}
int result = 0;
for(int i=31; i>=0; i--){
result = result<<1;
if(bitNumCount[i]%3!=0){
result += 1;
}
}
return result;
}
};上面用了一个32位的向量。经过优化，还可以更为精简：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result = 0;
int len = nums.size();
for(int i=0; i<32; i++){
int count = 0;
for(int j=0; j<len; j++){
count += (nums[j]>>i)&1;
}
result += (count%3)<<i;
}
return result;
}
};转载请注明：康瑞部落 » [LeetCode] Single Number II
0 条评论