Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

http://www.lintcode.com/en/problem/single-number-ii/

Discussion

用个hash （O(n) space）

位操作：数每一位上有多少个1，mod3为0说明该位上1出现3的倍数，若为1则说明只出现1一次。

Solution

用hash保存每个数出现的次数，O(n) space

class Solution {
public:
    /**
     * @param A : An integer array
     * @return : An integer 
     */
    int singleNumberII(vector<int> &A) {
        // write your code here
        int n = A.size();
        unordered_map<int, int> mymap;
        for(int i=0; i<n; i++) {
            if(mymap.find(A[i]) != mymap.end()) {
                mymap[A[i]] = mymap[A[i]]+1;
            } else {
                mymap[A[i]] = 1;
            }
        }
        for(int i=0; i<n; i++) {
            if(mymap[A[i]] == 1) {
                return A[i];
            } 
        }
    }
};

创建一个长度为sizeof(int) 的数组count[sizeof(int)]，count[i] 表示在在i 位 出现的1 的次数。如果count[i] 是3 的整数倍，则忽略；否则就把该位取出来组成答案。

// Time:  O(n)
// Space: O(1)
class Solution {
public:
    /**
     * @param A : An integer array
     * @return : An integer 
     */
    int singleNumberII(vector<int> &A) {
        int w = sizeof(int)*8;
        int result = 0;
        vector<int> count(w, 0);
        //count the number of 1 on each bit
        for(auto const& i : A) {
            for(int j=0; j<w; j++) {
                if(i >> j & 1) { //if j_th bit of i is 1 or not
                    count[j]++;
                    count[j] %=3;
                }
            }
        }
        for(int j=0; j<w; j++) {
            if(count[j] == 1) {
                result |= (1 << j);//same as result += (1 << j);
            }
        }
        return result;
    }
};