如何找出数组中两个只出现一次的数字
程序员文章站
2022-07-15 11:59:41
...
任何一个数字异或它自己都等于0,而0与任何数字求异或,都为原数字!
【思 路】首先我们考虑一个稍微简单点的情况:如果这个数组中只有一个数字出现且仅出现一次,其他数字都出现两次,我们应该怎么样找出这个数字呢?我们题目说数字出现两次有什么深意呢?我们很容易联想到异或运算,因为任何一个数字和自身异或的结果为0;知道了这点,我们就很容易知道,我们讲所有的数字进行异或,其结果就是仅出现一次的数字,因为其他所有的数字都两两异或为0了。
我们仍然讲原数组中的所有数字进行异或运算,容易知道,异或的结果实际上就是两个仅出现一次的数字的异或结果,因为这两个数字不相等,所以异或的结果肯定不为0,我们可以找到异或结果中,第一个为1的位,这说明在该位上,必然有一个数字为1,另一个数字在该为上为0;我们可以按照这个结果,对所有该位上为1的数字分为一组,而讲该位上为0的位分为另一组,这样我们就成功的讲原问题转换为两个简单的子问题。再对子问题全部异或,即可获得两个仅出现一次的数字。按照这个思路,我们可以得到如下的代码:
#include<iostream>
#include<string>
using namespace std;
//判断一个数number的第bitIndex位是否为1
bool IsBit1(int number,unsigned int bitIndex)
{
number = number>>bitIndex;
return (number & 1);
}
//找到num中第一个位是1的位
unsigned int FindFirstbitOf1(int num)
{
int bitIndex = 0;
while(bitIndex < 32 && ((num & 1) == 0))
{
num = num>>1;
bitIndex++;
}
//该函数的另一种循环结构,完全等价
/* for(bitIndex = 0;bitIndex < 32;++bitIndex,num = num>>1)
{
if((num & 1) ==1)
break;
}
*/
return bitIndex;
}
void FindNumbersAppearOnce(int data[],unsigned int length,int &num1,int &num2)
{
//无效输入
if(data == NULL || length < 2)
return;
//得到num1异或num2
int resultOfBitOR = 0;
for(int i = 0;i < length;++i)
{
resultOfBitOR ^= data[i];
}
//找到num1^num2的结果中第一个为1的位
unsigned int index = FindFirstbitOf1(resultOfBitOR);
num1 = 0;
num2 = 0;
//将index位的取值是否为1分为两组
//将每一组的全部数字做异或
for(int j= 0;j < length;++j)
{
if(IsBit1(data[j],index))
num1 ^= data[j];
else
num2 ^= data[j];
}
}
int main()
{
cout<<"Please Enter your ArrayLength:"<<endl;
int arraylength = 0;
cin>>arraylength;
int *array = new int[arraylength];
cout<<"Please Enter the numbers in your Array:"<<endl;
for(int k = 0;k < arraylength;++k)
{
cin>>array[k];
}
int result1 = 0;
int result2 = 0;
FindNumbersAppearOnce(array,arraylength,result1,result2);
cout<<"the numbers appear once in your array are:"<<endl;
cout<<result1<<"\t"<<result2<<endl;
return 0;
}
转载于:https://my.oschina.net/taisha/blog/59016