數組中隻出現一次的數字
-
- 題目描述
- 思路
- 題解
題目描述
一個整型數組裡除了兩個數字之外，其他的數字都出現了兩次。請寫程式找出這兩個隻出現一次的數字。
思路
這道題是典型的2n+2的問題，是2n+1問題的變種。
我們不如先來看，如何解決2n+1的問題：
一個整型數組裡除了一個數字之外，其他的數字都出現了兩次。請寫程式找出這個隻出現一次的數字。
我們可以利用異或運算的性質來求解：
0^a = a; 1^a = ~a; a^a = 0;
是以可以想見。如果我們将數組中所有元素的值相異或，其中兩兩成對的會得到結果0，而任何數與0異或得到的結果是其本身。此時，最終結果也就是落單的數與無數個0異或的結果，得到的結果值就是該落單的數的值。
我們已經利用異或的性質巧妙解決了2n+1的問題，時間複雜度為O(n)，空間複雜度為O(1)。
那麼我們能否将同樣的方法應用于2n+2的問題呢？
同樣思考，如果将所有元素相異或，得到的結果是什麼？是落單的兩個數相異或的值：a^b。
那麼a^b有什麼性質呢？我們如何通過該值擷取a和b的資訊？
認真分析題意，我們會發現還有一個隐含條件可以為我們利用，即a和b是不同的數。既然如此，a^b的值就不可能為0。一定至少有一位（二進制表示）的值為1。而a和b在該位上恰好不同。
不妨以該位上的值為依據，将2n+2的數分為兩組：2x+1和2y+1。（畢竟相同的數每一位都相同，是以可以保證成對的數最終被分到同一個組）。
此時2n+2的問題就被分解成了兩個2n+1的問題，按照以上的方法分别求解即可。
題解
//num1,num2分别為長度為1的數組。傳出參數
//将num1[0],num2[0]設定為傳回結果
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int result=0;
int i=0;
for(i=0;i<array.length;i++){
result ^= array[i];
}
i=0;
while(result>0){
if(result%2==1){
break;
}else{
result = result>>1;
i++;
}
}
int j = 1<<i;
for(i=0;i<array.length;i++){
if((array[i]&j)==0){
num1[0] ^= array[i];
}else{
num2[0] ^= array[i];
}
}
}
}