Single Number II

LeetCode #137

Description:

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.

Example:

Note

Idea:

不是最快的，但是很general的思想。用一个数组存int的每一位。

Code:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ndigit=8*sizeof(int);
        vector<int> digits(ndigit, 0);
        for(int i=0; i<nums.size(); ++i){
            for(int j=0; j<ndigit; ++j){
                digits[j] += (nums[i]>>j)&1;
                digits[j] %= 3;
            }
        }

        int result=0;
        for(int i=0; i<ndigit; i++){
            result += (digits[i] << i);
        }
        return result;
    }
};