找出能够区分两个不同数的位,用这个位将数组分为两个部分,其中每部分只有一个出现次数为1的数。
数组中只出现一次的数字
http://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811
找出能够区分两个不同数的位,用这个位将数组分为两个部分,其中每部分只有一个出现次数为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; } } }