Single Number II

题目：

Given 3*n + 1 numbers, every numbers occurs triple times except one, find it.

其实这道题目可以被理解为通用模板：

Given an array of integers, every element appears k (k >1) times except for one, 
which appears p times(p>=1, p % k != 0). Find that single one.

分析：

解法1 是no extra space的，解法1用的是类似问题的通用模板，也就是一个状态机的感觉。通用模板的思路如下：

通用模板是怎么来的呢，获取通用模板的思路如下：
(0) 

(1) 首先，你要记录大多数元素出现过k次，就需要一个counter，由于你要用bit operation来
改变你counter的数字，相同的时候就+1，那么你只能用or或者xor，因为and操作你做counter & i
会导致如果i是0，他就刷回0了，而不是加1.

(2) 然后，因为你二进制的counter是00->01->10->11...这样增加的，有个从01到10的过程，所以，
为了能让最低位从1变回0，你不能用or，而是必须用xor。

(3) 每次你想进位counter的x2位置的时候，有两个要求，第一个，你的x1位已经是1了；第二个，现在
的A[i]等于你正在数的这个数字，所以其实x2 = (x2 ^ x1) & (x2 ^ A[i])，如果你用一下结合律
也就是x2 = x2 ^ (x1 & A[i])

(4) 不能让counter无限制的递增，每次数到k之后需要归零。这个归零的操作用x = x & mask来解决。

(5) mask的值应该是多少呢？如果k == 5，你的couter有3bit，那么当counter == 101的时候你需要
把他归零，也就是说，你的mask需要和counter反过来，也就是mask == 010，也就是
maxk == ~x1 & x2 & ~x3 == ~(x1 & ~x2 & x3)

(6) 最后让你的x1, x2, x3,..., xm 都去 &= mask就好了。

(7) 截至目前为止，你知道你需要一个m-bit的counter，m的值取决于k的大小，m > log(k)就可以。然后
如果你要做的不是1bit的输入，而是32bit int的输入，怎么办？答案是你可以用32个m-bit的counter分别来
记录int中的的每一个bit就可以。

(8) 但是我们知道，bit操作是相对独立的，一个32 x m的counter和一个m x 32的counter实质上没有差别
于是，我们用m个32bit的寄存器（或者说m个int寄存器）就可以搞定。

(9) 最后的返回值是什么？返回值是x1因为，x1里面记录的是所有出现1次元素的信息，x2里面记录的是出现1次和2次
的元素的混合信息，以此类推。这是因为你的m x 32寄存器是横着看还是竖着看的缘故。于是乎，如果p = 2 = 10B
的时候怎么办？我们返回x2就好，如果p = 3 = 11B怎么办？返回x1 或者 x2，如果p = 4 = 100B呢？返回x3
就可以了。

解法2 是extra space的。解法2更容易想到，但是要注意loop through hash_table的方法应该用：

for (auto it = Hash.begin(); it != Hash.end(); it++) {
    if (it->second == 1) {
        return it->first;
    }
}

解法1：

class Solution {
public:
    /**
     * @param A : An integer array
     * @return : An integer 
     */
    int singleNumberII(vector<int> &A) {
        // write your code here
        int x1 = 0;
        int x2 = 0;
        int mask = 0;
        for (int i = 0; i < A.size(); i++) {
            x2 = x2 ^ (x1 & A[i]);
            x1 = x1 ^ A[i];
            mask = ~(x1 & x2);
            x2 = x2 & mask;
            x1 = x1 & mask;
        }
        return x1;
    }
};

解法2：

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