程序員面試題精選100題(63)-數組中三個只出現一次的數字[算法]
- 面試
- 關注:3.88K次
題目:一個數組中有三個數字a、b、c只出現一次,其他數字都出現了兩次。請找出三個只出現一次的數字。
分析:我們討論瞭如何在一個數組中找出兩個只出現一次的數字。在這道題中,如果我們能夠找出一個只出現一次的數字,剩下兩個只出現一次的數字就很容易找出來了。
如果我們把數組中所有數字都異或起來,那最終的結果(記為x)就是a、b、c三個數字的異或結果(x=a^b^c)。其他出現了兩次的數字在異或運算中相互抵消了。
我們可以證明異或的結果x不可能是a、b、c三個互不相同的數字中的任何一個。我們用反證法證明。假設x等於a、b、c中的某一個。比如x等於a,也就是a=a^b^c。因此b^c等於0,即b等於c。這與a、b、c是三個互不相同的三個數相矛盾。
由於x與a、b、c都各不相同,因此x^a、x^b、x^c都不等於0。
我們定義一個函數f(n),它的結果是保留數字n的二進制表示中的最後一位1,而把其他所有位都變成0。比如十進制6表示成二進制是0110,因此f(6)的結果為2(二進制為0010)。f(x^a)、f(x^b)、f(x^c)的結果均不等於0。
接着我們考慮f(x^a)^f(x^b)^f(x^c)的結果。由於對於非0的'n,f(n)的結果的二進制表示中只有一個數位是1,因此f(x^a)^f(x^b)^f(x^c)的結果肯定不為0。這是因為對於任意三個非零的數i、j、k,f(i)^f(j)的結果要麼為0,要麼結果的二進制結果中有兩個1。不管是那種情況,f(i)^f(j)都不可能等於f(k),因為f(k)不等於0,並且結果的二進制中只有一位是1。
於是f(x^a)^f(x^b)^f(x^c)的結果的二進制中至少有一位是1。假設最後一位是1的位是第m位。那麼x^a、x^b、x^c的結果中,有一個或者三個數字的第m位是1。
接下來我們證明x^a、x^b、x^c的三個結果第m位不可能都是1。還是用反證法證明。如果x^a、x^b、x^c的第m位都是1,那麼a、b、c三個數字的第m位和x的第m位都相反,因此a、b、c三個數字的第m位相同。如果a、b、c三個數字的第m位都是0,x=a^b^c結果的第m位是0。由於x和a兩個數字的第m位都是0,x^a結果的第m位應該是0。同理可以證明x^b、x^c第m位都是0。這與我們的假設矛盾。如果a、b、c三個數字的第m位都是1,x=a^b^c結果的第m位是1。由於x和a兩個數字的第m位都是1,x^a結果的第m位應該是0。同理可以證明x^b、x^c第m位都是0。這還是與我們的假設矛盾。
因此x^a、x^b、x^c三個數字中,只有一個數字的第m位是1。於是我們找到了能夠區分a、b、c三個數字的標準。這三個數字中,只有一個數字滿足這個標準,而另外兩個數字不滿足。一旦這個滿足標準數字找出來之後,另外兩個數字也就可以找出來了。
這種思路的C++代碼如下:
void getThreeUnique(vector
{
if(() < 3)
return;
int xorResult = 0;
vector
for(; iter != (); ++iter)
xorResult ^= *iter;
int flags = 0;
for(iter = n(); iter != (); ++iter)
flags ^= lastBitOf1(xorResult ^ *iter);
flags = lastBitOf1(flags);
// get the first unique number
int first = 0;
for(iter = n(); iter != (); ++iter)
{
if(lastBitOf1(*iter ^ xorResult) == flags)
first ^= *iter;
}
_back(first);
// move the first unique number to the end of array
for(iter = n(); iter != (); ++iter)
{
if(*iter == first)
{
swap(*iter, *(() - 1));
break;
}
}
// get the second and third unique numbers
getTwoUnique(n(), () - 1, unique);
}
int lastBitOf1(int number)
{
return number & ~(number - 1);
}
void getTwoUnique(vector
{
int xorResult = 0;
for(vector
xorResult ^= *iter;
int diff = lastBitOf1(xorResult);
int first = 0;
int second = 0;
for(vector
{
if(diff & *iter)
first ^= *iter;
else
second ^= *iter;
}
_back(first);
_back(second);
}
上文中getThreeUnique從數組中找出三個只出現一次的數字,而getTwoUnique從數組中找出兩個只出現一次的數字。lastBitOf1實現分析中的函數f(n)的功能,它只保留數字n的二進制表示中的最後一位1,而把其他所有位都變成0。
在函數getThreeUnique中,我們通過第一個for循環把a、b、c三個數字異或的結果保存到xorResult中,接着在第二個for循環中求出f(x^a)^f(x^b)^f(x^c)並保存到變量flags中。在語句flags=lastBitOf1(flags)求出f(x^a)^f(x^b)^f(x^c)結果的二進制中最後一位是1的位。並根據這一數位求出第一個只出現一次的數字first。接着把first交換到數組的最後,並在數組的前n-1個數字中求出另外兩個只出現一次的數字。
- 文章版權屬於文章作者所有,轉載請註明 https://xuewengu.com/flzc/mianshi/9nqk7l.html