题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
if(array.length < 2){
return;
}
int n = 0;
for(int i = 0; i < array.length; i++){
n ^= array[i];
}
int last = n - ((n - 1) & n);
for(int i = 0; i < array.length; i++){
if( ( last & array[i]) == 0){
num1[0] ^= array[i];
}else{
num2[0] ^= array[i];
}
}
}
}
- 两个同样的数相异或后等于0
- 两个一样的数a的和一个不一样b的数相异或后 (a ^ b ^ a)结果为b,并且与顺序无关
- a ^ b ^ c ^ d ^ e ^ d ^ c ^ b ^ a = e
- 利用这个条件,我们将所有的数都异或一遍,将得到要求的两个数相&的结果。(a ^ b ^ c ^ d ^ a ^ d = b ^ c)
- 然后利用一个公式求出b和c之间的一个有差异的位,并按照这个位的值不同,将数组分为两组(aca,bdd) 然后分别再分别在两个组里全部相异或一次(a ^ c ^ a, b ^ d ^ d)
- 这个表示差异的位的信息存在last里面,last是用来求一个二进制数的最后一个1的位置的算法(n = 10001100,(n - 1) & n= 10001000,last = 100)
网友评论