[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?

偷偷地看了一下tag，是位操作，之前也做过这样的题目，感觉对这方面不是很熟悉，想不出来=.=
看了网上的解题思路之后才会。再记录一下思路：题目的的意思是所有数字都出现三次，只有一个数字出现一次(只出现一次而不是两次)。因为int型数字可以使用32位二进制数表示，所以使用一个bit数组记录这些数字(二进制)每一位的数字出现1的个数。如果1出现的次数不是3的整数倍（模三余一）则就是那个数字。

不是3，应用到k也是成立的。将模三改为模k就可以了。

class Solution {
public:
    int singleNumber(int A[], int n) {
        if(A==NULL||n==0) return 0;
        int ans = 0,i,j;
        int bit[32] = {0};
        for(i=0;i<32;i++){
            for(j=0;j<n;j++)
                bit[i] += (A[j]>>i)&1;
            }
            //按位构造答案
            ans |= (bit[i]%3)<<i;
        }
        return ans;
    }
};