思路:
(1)一个数字异或它本身等于0,所以如果一个数组中只存在一个出现一次的数字,那么这个数组所有的元素异或,就是这个只出现一次的数字。
(2)可以把这个数组所有的元素相异或,所得只是这两个元素异或的结果,找到这个结果中第一位1,那么可以根据此位是否为1,来把数组分为两个部分,那么这两个不同的元素,肯定会被分到不同的两个数组中,并且其他相同元素,都会被两两成对的分到对应得元素中。在分别对这两个子数组求异或,即为所得结果。
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
if(array==null||array.length<2)
return;
int xorResult=0;
for(int i=0;i<array.length;i++){
xorResult^=array[i];
}
int index=findFirstBitIs1(xorResult);
for(int i=0;i<array.length;i++){
if(isBit1(array[i],index))
num1[0]^=array[i];
else
num2[0]^=array[i];
}
}
public int findFirstBitIs1(int num){
int index=0;
while(((num&1)==0)&&(index<32)){
num=num>>1;
index++;
}
return index;
}
public boolean isBit1(int num,int index){
num=num>>index;
return (num&1)==1;
}
}