思路:
(1)一個(gè)數(shù)字異或它本身等于0首尼,所以如果一個(gè)數(shù)組中只存在一個(gè)出現(xiàn)一次的數(shù)字耙替,那么這個(gè)數(shù)組所有的元素異或,就是這個(gè)只出現(xiàn)一次的數(shù)字胶逢。
(2)可以把這個(gè)數(shù)組所有的元素相異或厅瞎,所得只是這兩個(gè)元素異或的結(jié)果,找到這個(gè)結(jié)果中第一位1初坠,那么可以根據(jù)此位是否為1和簸,來(lái)把數(shù)組分為兩個(gè)部分,那么這兩個(gè)不同的元素碟刺,肯定會(huì)被分到不同的兩個(gè)數(shù)組中锁保,并且其他相同元素,都會(huì)被兩兩成對(duì)的分到對(duì)應(yīng)得元素中半沽。在分別對(duì)這兩個(gè)子數(shù)組求異或爽柒,即為所得結(jié)果。
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;
}
}