数组中只出现一次的数字进阶（其余数字均出现3次）

题目描述：

一个整型数组里除了一个数字只出现一次之外，其他的数字都出现了3次。请写程序找出这个只出现一次的数字。

思路：

出现3次就不能再用异或的方法了，因为三个相同的数异或还是得到本身。但是还是可以采用位运算的思想，因为出现三次的数字每个位（0或者1）也是出现三次，因此可以每一位的和能够被3整除（对3取余为0）。所以如果把每个数的二进制表示的每一位加起来，对于每一位的和，如果能被3整除，那对应那个只出现一次的数字的那一位就是0，否则对应的那一位是1。

我们需要用一个长度为32（int型二进制表示最多为32位，4字节）的数组bitSum保存每一位的和，具体来讲实现过程是，先初始化为0，然后对于每个数字，遍历它二进制表示的每一位，如果这一位是1，bitSum对应的那一位就加1。

时间复杂度为O(n)

int FindNumberAppearingOnce(vector<int> numbers)
{
int bitSum[32]={0};
for(int i=0;i<numbers.size();i++)
{
int bit=1;//对于每个数都从最低位开始判断
for(int j=31;j>=0;j--)
{
if(numbers[i]&bit==1)
bitSum[j]++;
bit=bit<<1;//接下来判断高一位
}
}
int result=0;
for(int j=0;j<32;j++)
{
result=result<<1;//先把当前结果左移到高位
result+=bitSum[j]%3;//然后把当前位应该为0还是1填上去
}
return result;
}

最后

以上就是醉熏冷风为你收集整理的数组中只出现一次的数字进阶（其余数字均出现3次）的全部内容，希望文章能够帮你解决数组中只出现一次的数字进阶（其余数字均出现3次）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。