描述:
一个整型数组里除了两个数字之外,其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。
分析:
根据本题的题干可以得知,所需要求解的数组,只有两个数字是单独出现的,其余的数字均为成对出现。
补充:求解一个数组中只出现一次的数字,其余数字是出现了偶数次。只需要将这个数组的所有元素逐一做异或运算得到的结果便是这个单独出现的数字。这是因为做异或运算的时候,相同的数字的结果为0,任何数字与0异或均为其本身。
那么,这一题可以看成两个单独出现数字的数组的组合。解答步骤如下:
- 将数组所有元素做异或运算,这个结果就相当于两个单独出现数字做异或运算的结果;
- 因为在二进制情况下, 这两个不同的数字,必然有一位不相等,那么按照这个位数对这个数组进行分割,由于相同的数字的每一位一定对应相等,那么这样分割的数组必然满足只有一个单独出现的数字;
- 分别对于这两个数组做异或运算,得到的结果便是这两单独出现的数字。
代码实现:
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int len=array.length;
if (len==2){
num1[0]=array[0];
num2[0]=array[1];
}
int bitReslut=0;
for (int i=0;i<len;i++){
bitReslut^=array[i];
}
int index = findFirst1(bitReslut);
for (int i=0;i<len;i++){
if (((array[i]>>index)&1)==0){
num1[0]^=array[i];
}else {
num2[0]^=array[i];
}
}
}
/**
寻找第一个为1的位数
*/
private int findFirst1(int bit){
int index=0;
while (((bit&1)==0)&&index<32){
bit=bit>>1;
index++;
}
return index;
}