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.

題意：有一個數組，只有一個數出現一次，其他的都出現三次，找出一次的數

思路：首先我們想到是每次把每一位二進制上1的個數都mod3，然後就能找出一個的了，但是這樣空間太大了，所以我們想能記錄每一次出現三次的時候就清0，那麼我們需要先記錄1次的，然後記錄2次的，這樣就能求出三次的了，最後再更新出現1次和2次的(也就是清0出現三次的位置)，最後one代表的就是出現1次的了，

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