牛客网刷题|数组中只出现一次的数字
程序员文章站
2022-03-01 13:33:14
...
题目来源:牛客网
题目描述
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
题目解析:
使用异或,两个相同的数字异或会等于0;
若只存在一个数,一直异或就会把这个数生下来;
若两个数,一直异或,这两个不同的数异或之后会生成一个数,某位上一定会出现1,则表示这个位上,两数不同;根据这个位,将数组分成两组,每组即只存在一个不同的数。
代码:
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
if(data.size()<2)
return;
int index = data[0];
for(int i=1; i<(int)data.size(); i++)
{
index ^= data[i];
}
if(index==0)
return ;
int nbit = Getbit(index);
for(int i =0;i<(int)data.size();i++)
{
if(isbit(data[i],nbit))
{
* num1 ^= data[i];
}
else
{
* num2 ^= data[i];
}
}
}
int Getbit(int num)
{
int index = 0;
while((num&1)==0)
{
index++;
num = num>>1;
}
return index;
}
bool isbit(int num,int index)
{
num = num>>index;
return num&1;
}
};
上一篇: c语言二进制输出
下一篇: 牛客刷题数组之数组中只出现一次的数字