一、 题目
给一个数组，其中只有一个数出现一次，其他的数都出现3次，请找出这个数。要求时间复杂度是O(n)，空间复杂度O(1)。
二、 分析
第一次遇见这样的题，真心没思路….前面的signal number中我们可以直接异或得到结果，很显然这个更复杂了。暴力解法或排序显然无法满足时空要求，所以还得回到位运算上，既然是同样的数出现了三次，我们可以想到他们的二进制表达对应的位置上相同。对于除出现一次之外的所有的整数，其二进制表示中每一位1出现的次数是3的整数倍，将所有这些1清零，剩下的就是最终的数。如果我们在每一个位置上取到出现1的次数，并进行余3操作，则可消除该数。
例如:A[]={2,3,4,3,2,2,3}
0010
0011
0100
0011
0010
0010
0011
= -0-1-6-3-(1的个数)
0100
int型数据为32位，可以开一个大小为32的int型数组存储N个元素的各个二进制位的1出现的次数，然后将该次数模3运算。
PS:后面几种方法刚开始真心没看懂….自己弱菜
class Solution {
public:
int singleNumber(int A[], int n) {
int bitint[32]={0};
int ans=0;
for(int i=0; i<32; i++){
for(int j=0; j
>i)&1;
}
ans|=(bitint[i]%3)<