Leetcode :: Single Number II

Leetcode :: 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 I 是把所有都異或，最後就是答案，很明了；可是這裡有3個，應該怎麼辦呢？

出現了三次的時候，如果仍然從位運算入手，特征是什麼？設那個唯一的數是x，特征是，按int型32位計，其中某一位假設x在該位上是0，則情況應該是該位的1出現的次數是3的倍數，而如果是1，則應該是出現3n + 1次的1，根據這個特征，來計算那個唯一的數據；

設三個int， one、two、three，這裡出現一次為 0 1 兩次未 1 0 三次為 1 1 這裡的高位是存在two中，低位存在one中，根據不同狀態去做操作；同時為1則清0. 再強調一下，這裡one表示的每一位在低位的計數表示，two表示每一位在高位的計數表示；

public:
    int singleNumber(int A[], int n) {
        int one = 0, two = 0, three = 0;
        for (int i = 0; i < n; i++){
            two |= one & A[i];      //be careful
            one ^= A[i];
            three = one & two;
            one &= ~three;
            two &= ~three;
        }
        return one;
    }

這裡be careful two可以用異或，因為不可能出現one two在相同位同時為1的情況，所以異或和或是一樣的，但是邏輯上，應該是選用或 ，更能表現這個算法的意思；