Single Number II，singlenumberii

Single Number II，singlenumberii

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?

解題思路：

1.利用二進制中的位運算，有n*3個相同的數相加，那麼其二進制的每一位必定是3的倍數

2.剩下的那個單獨的數，就是每一位除以3的余數，之後在把每一位轉換成十進制相加，總和就是單獨的那個數。

 1 int singleNumber(int* nums, int numsSize) {
 2     int ary[32] = {0};
 3     int res = 0;
 4     int i;
 5     int j;
 6     for(i = 0; i < 32; i++)
 7     {
 8         for(j = 0; j < numsSize; j++)
 9         {
10             ary[i] += ((nums[j] >> i) & 1);
11             ary[i] = ary[i] % 3;
12         }
13         res |= (ary[i] << i);
14     }
15     return res;
16 }

轉：http://blog.csdn.net/feliciafay/article/details/19004479