面試100 34找出數(shù)組中唯一出現(xiàn)一次的兩個數(shù)字
一問題描述
一個數(shù)組中，存在兩個只出現(xiàn)一次的數(shù)字，其余的數(shù)字均出現(xiàn)兩次。要求在時間復(fù)雜度o(n)，空間復(fù)雜度為o(1)的情況下找出這兩個數(shù)字。
二 問題分析
此題實際考察了，對位操作的理解。首先進(jìn)行簡化，考慮只有一個數(shù)組中，只存在出現(xiàn)了一次的一個數(shù)字，其余數(shù)字在數(shù)組中出現(xiàn)兩次，試
找出這個數(shù)字。
三 解決方案
首先 回憶 異或操作，任意數(shù)字與自身相異或，結(jié)果都為0.
還有一個重要的性質(zhì)，即任何元素與0相異或，結(jié)果都為元素自身。
解決方案：
1 從數(shù)組的起始位置開始，對元素執(zhí)行異或操作，則最后的結(jié)果，即為此只出現(xiàn)了一次的元素。
2 題目中，數(shù)組中存在兩個不同的元素，若是能仿造上述的解決方案，將兩個元素分別放置在兩個數(shù)組中，然后分別對每個數(shù)組進(jìn)行異或操作，
則所求異或結(jié)果即為所求。
3 首先對原數(shù)組進(jìn)行全部元素的異或，得到一個必然不為0的結(jié)果，然后判斷該結(jié)果的2進(jìn)制數(shù)字中，為1的最低的一位。
然后根據(jù)此位是否為1 ，可以把原數(shù)組分為兩組。則兩個不同的元素，必然分別在這兩個數(shù)組中。
4 然后對兩個數(shù)組，進(jìn)行異或操作，即可得到所求。
四 代碼示例
#include <iostream>
using namespace std ;
const int N = 10 ;
int getSingle(int * a) //獲取全部元素的異或結(jié)果
{
if(!a)
return -1;
int sum = a[0] ;
for(int i = 1; i < N; i++)
sum ^= a[i] ;
return sum ;
}
int getTwo(int * a ,int & one , int & two , int sum) //求數(shù)組中兩個不同的元素
{
unsigned int flag = 1;
while(flag) //求異或結(jié)果，最低的為1的二進(jìn)制位，根據(jù)此位是否為1，將元素分為兩組，兩個不同的元素，在此位必然，一個為1，一個為0
{
if(flag&sum)
break;
flag = flag << 1 ;
}
//下面將flag與每個元素相求與，根絕結(jié)果是否為1，將其化為兩個數(shù)組
//分別計算每個數(shù)組的異或結(jié)果，并將結(jié)果，存儲分別存儲在one和two中。
one = two = 0 ;//0與任何數(shù)異或都為其自身，所以初始化的時候，應(yīng)該初始化為0
for(int i = 0 ; i < N ;i++ )
{
if(a[i] & flag)
{
one ^= a[i] ;
}
else
{
two ^= a[i] ;
}
}
}
int main()
{
int a[N] = {3 , 5 ,8 , 8 , 5 , 3 ,1 ,4 ,4,10} ;
int single = getSingle(a) ;
int one = 0 ;
int two = 0;
getTwo(a ,one , two ,single) ;
cout<<single<<" "<<one<<" "<<two<<endl ;
system("pause") ;
return 0 ;
}