剑指offer 56-2:数组中唯一只出现一次的数字
程序员文章站
2022-07-15 10:37:34
...
此题是求数组中唯一只出现一次的数字,其他数字均出现了三次
/**
*Copyright @ 2019 Zhang Peng. All Right Reserved.
*Filename:
*Author: Zhang Peng
*Date:
*Version:
*Description:
**/
#include<iostream>
#include<vector>
using namespace std;
int FindOnlyNum(vector<int> data)
{
int bitcount[32] = {0};
//记录各二进制位数上1出现的次数
for (int i = 0; i < data.size(); i++)
{
int v = data[i];
int index = 1;
for (int j = 31; j >=0; j--)
{
int num = index&v;
if (num != 0)
bitcount[j] += 1;
index=index << 1;
}
}
//将各位整除3以后余下的个数组合在一起
int result = 0;
for (int k = 0; k < 32; k++)
{
result = result << 1;
result += bitcount[k] % 3;
}
return result;
}
int main()
{
vector<int> data = { 1, 2, 3, 4, 1, 1, 2, 2, 4, 4 };
cout << FindOnlyNum(data) << endl;
system("pause");
return 0;
}