數(shù)組中只出現(xiàn)一次的數(shù)字
題目描述
一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次剃执。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。
//num1,num2分別為長度為1的數(shù)組懈息。傳出參數(shù)
//將num1[0],num2[0]設(shè)置為返回結(jié)果
public class Solution {
/*解題思路：
首先我們考慮這個問題的一個簡單版本：一個數(shù)組里除了一個數(shù)字之外肾档，其他的數(shù)字都出現(xiàn)了兩次黍瞧。請寫程序找出這個只出現(xiàn)一次的數(shù)字上忍。
這個題目的突破口在哪里？題目為什么要強調(diào)有一個數(shù)字出現(xiàn)一次禽车，其他的出現(xiàn)兩次姑宽？我們想到了異或運算的性質(zhì)：任何一個數(shù)字異或它自己都等于0遣耍。
也就是說，如果我們從頭到尾依次異或數(shù)組中的每一個數(shù)字炮车，那么最終的結(jié)果剛好是那個只出現(xiàn)一次的數(shù)字舵变，因為那些出現(xiàn)兩次的數(shù)字全部在異或中抵消
掉了。有了上面簡單問題的解決方案之后瘦穆，我們回到原始的問題纪隙。如果能夠把原數(shù)組分為兩個子數(shù)組。在每個子數(shù)組中难审，包含一個只出現(xiàn)一次的數(shù)字瘫拣，而
其它數(shù)字都出現(xiàn)兩次。如果能夠這樣拆分原數(shù)組告喊，按照前面的辦法就是分別求出這兩個只出現(xiàn)一次的數(shù)字了麸拄。
我們還是從頭到尾依次異或數(shù)組中的每一個數(shù)字，那么最終得到的結(jié)果就是兩個只出現(xiàn)一次的數(shù)字的異或結(jié)果黔姜。因為其它數(shù)字都出現(xiàn)了兩次拢切，在異或中全
部抵消掉了。由于這兩個數(shù)字肯定不一樣秆吵，那么這個異或結(jié)果肯定不為0淮椰，也就是說在這個結(jié)果數(shù)字的二進制表示中至少就有一位為1。我們在結(jié)果數(shù)字中
找到第一個為1的位的位置纳寂，記為第N位≈魉耄現(xiàn)在我們以第N位是不是1為標準把原數(shù)組中的數(shù)字分成兩個子數(shù)組，第一個子數(shù)組中每個數(shù)字的第N位都為1毙芜，
而第二個子數(shù)組的每個數(shù)字的第N位都為0『雒剑現(xiàn)在我們已經(jīng)把原數(shù)組分成了兩個子數(shù)組，每個子數(shù)組都包含一個只出現(xiàn)一次的數(shù)字腋粥，而其它數(shù)字都出現(xiàn)了
兩次晦雨。*/
public void FindNumsAppearOnce(int [] array,int num1[], int num2[]) {
if(array==null ||array.length<2)
return ;
int temp = 0;
for(int i=0;i<array.length;i++)
temp ^= array[i];//將array數(shù)組中的每一位按位逐一進行異或架曹，例如a=4'b1010，則b=1^0^1^0=0
int indexOf1 = findFirstBitIs(temp);
for(int i=0;i<array.length;i++){
if(isBit(array[i], indexOf1))
num1[0]^=array[i];
else
num2[0]^=array[i];
}
}
//假設(shè)異或結(jié)果二進制表示中為1的位置為N
public int findFirstBitIs(int num){
int indexBit = 0;
while(((num & 1)==0)&&(indexBit)<32){//num的二進制與1的二進制&操作
num = num >> 1;//num右移一位
++indexBit;
}
return indexBit;//右移了幾位
}
//
public boolean isBit(int num,int indexBit){
num = num >> indexBit;
return (num & 1) == 1;
}
}
