找出能够区分两个不同数的位,用这个位将数组分为两个部分,其中每部分只有一个出现次数为1的数。
异或的性质:相同数字异或的结果为0.
先区分。然后再计算。
diff&=-diff,计算最右侧不为0的位。
/**
* 一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
* @param array 整型数组
* @param num1 num1[0]为返回结果
* @param num2 num2[0]为返回结果
*/
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int diff=0;
for(int num :array){
diff^=num;
}
// 最右侧不为 0 的位。通过这个位将数组分为两部分,每部分只有一个出现一次的数。
diff&=-diff;
for(int num:array){
if ((diff & num) == 0) {
num1[0]^=num;
}else{
num2[0]^=num;
}
}
}



京公网安备 11010502036488号