EEPW论坛

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?

思路：若一个数出现三次，则其对应的二进制数每一位相加必为3或者0。统计数组中元素的每一位，若为3的倍数，所求数的二进制位对3取余为0

否则为1

1. class Solution  

2. {  

3. public:  

4.     int singleNumber(int A[], int n)  

5.     {  

6.         int bit[32] = {0};  

7.         int res = 0;  

8.         for (int i=0; i<32; i++)  

9.         {  

10.             for (int j = 0; j < n; j++)  

11.             {  

12.                 bit[i] += (A[j] >> i) & 1;  

13.                 res |= (bit[i]%3)<<i;  

14.             }  

15.         }  

16.   

17.         return res;  

18.     }  

19. };