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?

class Solution {
public:
    int singleNumber(int A[], int n) {
#if 0
		int ans[32] = {0};
		int res = 0;
		for (int i = 0; i < 32; i++)
		{
			for (int j = 0; j < n; j++)
			{
				ans[i] += (A[j] >> i) & 1;
			}
			res |= (ans[i] % 3) << i;
		}
		return res;
#endif // 1
		//一般解法，可以統計每個數字的每位bit的1的個數，最後的mod 3得到結果
#if 1
		int one = 0, two = 0, three = 0;
		for (int i = 0; i < n; i++)
		{
			two |= one & A[i];
			one ^= A[i];
			three = one & two;
			one &= ~three;
			two &= ~three;
		}
		return one;
#endif // 1
		//one標記為當前數組成員為止，二進制中1出現1次，two標記二進制中1出現2次，
		//three標記二進制中1出現3次，那麼，當three = one & two,如果，某一個位
		//one和two都有，那麼，肯定是出現了三次，然後 ~three，則清除那些出現三次的數字
    }
};