(数组)只出现一次的数
转载:https://www.cnblogs.com/AndyJee/p/4473436.html
题目:
1、给一数组,所有的数都出现了两次,只有一个数出现了一次,求这个数。
2、给一数组,所有的数都出现了两次,只有两个数出现了一次, 求这两个数。
思路:
位运算
1、将数组里所有的数都做异或操作,因为相同的数异或之后就等于0,所以结果就是只出现一次的那个数。
2、同样将数组里所有的数做异或操作,相同的数异或之后就等于0,所以结果就是只出现一次的两个数的异或结果,因为两个数不相同,所以异或结果不为0,必定在某个bit位上存在‘1’,将所有的数在这一位上按0,1分开。假设所有该位为1的异或结果为x,所有该位为0的异或结果为y,则只出现一次的两个数分别为x,y。
代码:
1、只出现一次的一个数
2、只出现一次的两个数
#include <iostream>
using namespace std;
// one number appears once while others appears twice
int appearOnceNum(int A[],int n){
int XxorY=0;
for(int i=0;i<n;i++)
XxorY^=A[i];
return XxorY;
}
// two number appears once while others appears twice
void appearOnceNums(int A[],int n,int &x,int &y){
int XxorY=0;
for(int i=0;i<n;i++)
XxorY^=A[i];
int mask=1;
while((XxorY&mask)==0)
mask<<=1;
x=0;
y=0;
for(int i=0;i<n;i++){
if(A[i]&mask)
x^=A[i];
else
y^=A[i];
}
}
int main()
{
int A[]={2,3,2,4,4,7,9,9,7};
int an=sizeof(A)/sizeof(A[0]);
cout << appearOnceNum(A,an)<< endl;
int B[]={2,3,2,4,4,7,9,7};
int bn=sizeof(B)/sizeof(B[0]);
int x=0,y=0;
appearOnceNums(B,bn,x,y);
cout<<x<<" "<<y<<endl;
return 0;
}