程序員面試題精選100題(63)-數(shù)組中三個(gè)只出現(xiàn)一次的數(shù)字[算法]

題目：一個(gè)數(shù)組中有三個(gè)數(shù)字a、b、c只出現(xiàn)一次，其他數(shù)字都出現(xiàn)了兩次。請(qǐng)找出三個(gè)只出現(xiàn)一次的數(shù)字。

分析：我們討論了如何在一個(gè)數(shù)組中找出兩個(gè)只出現(xiàn)一次的數(shù)字。在這道題中，如果我們能夠找出一個(gè)只出現(xiàn)一次的數(shù)字，剩下兩個(gè)只出現(xiàn)一次的數(shù)字就很容易找出來了。

如果我們把數(shù)組中所有數(shù)字都異或起來，那最終的結(jié)果（記為x）就是a、b、c三個(gè)數(shù)字的異或結(jié)果（x=a^b^c）。其他出現(xiàn)了兩次的數(shù)字在異或運(yùn)算中相互抵消了。

我們可以證明異或的結(jié)果x不可能是a、b、c三個(gè)互不相同的數(shù)字中的任何一個(gè)。我們用反證法證明。假設(shè)x等于a、b、c中的某一個(gè)。比如x等于a，也就是a=a^b^c。因此b^c等于0，即b等于c。這與a、b、c是三個(gè)互不相同的三個(gè)數(shù)相矛盾。

由于x與a、b、c都各不相同，因此x^a、x^b、x^c都不等于0。

我們定義一個(gè)函數(shù)f(n)，它的結(jié)果是保留數(shù)字n的二進(jìn)制表示中的最后一位1，而把其他所有位都變成0。比如十進(jìn)制6表示成二進(jìn)制是0110，因此f(6)的結(jié)果為2（二進(jìn)制為0010）。f(x^a)、f(x^b)、f(x^c)的結(jié)果均不等于0。

接著我們考慮f(x^a)^f(x^b)^f(x^c)的結(jié)果。由于對(duì)于非0的n，f(n)的結(jié)果的二進(jìn)制表示中只有一個(gè)數(shù)位是1，因此f(x^a)^f(x^b)^f(x^c)的結(jié)果肯定不為0。這是因?yàn)閷?duì)于任意三個(gè)非零的數(shù)i、j、k，f(i)^f(j)的結(jié)果要么為0，要么結(jié)果的二進(jìn)制結(jié)果中有兩個(gè)1。不管是那種情況，f(i)^f(j)都不可能等于f(k)，因?yàn)閒(k)不等于0，并且結(jié)果的二進(jìn)制中只有一位是1。

于是f(x^a)^f(x^b)^f(x^c)的結(jié)果的二進(jìn)制中至少有一位是1。假設(shè)最后一位是1的位是第m位。那么x^a、x^b、x^c的結(jié)果中，有一個(gè)或者三個(gè)數(shù)字的第m位是1。

接下來我們證明x^a、x^b、x^c的三個(gè)結(jié)果第m位不可能都是1。還是用反證法證明。如果x^a、x^b、x^c的第m位都是1，那么a、b、c三個(gè)數(shù)字的第m位和x的第m位都相反，因此a、b、c三個(gè)數(shù)字的第m位相同。如果a、b、c三個(gè)數(shù)字的第m位都是0，x=a^b^c結(jié)果的第m位是0。由于x和a兩個(gè)數(shù)字的第m位都是0，x^a結(jié)果的第m位應(yīng)該是0。同理可以證明x^b、x^c第m位都是0。這與我們的假設(shè)矛盾。如果a、b、c三個(gè)數(shù)字的第m位都是1，x=a^b^c結(jié)果的第m位是1。由于x和a兩個(gè)數(shù)字的第m位都是1，x^a結(jié)果的第m位應(yīng)該是0。同理可以證明x^b、x^c第m位都是0。這還是與我們的假設(shè)矛盾。

因此x^a、x^b、x^c三個(gè)數(shù)字中，只有一個(gè)數(shù)字的第m位是1。于是我們找到了能夠區(qū)分a、b、c三個(gè)數(shù)字的標(biāo)準(zhǔn)。這三個(gè)數(shù)字中，只有一個(gè)數(shù)字滿足這個(gè)標(biāo)準(zhǔn)，而另外兩個(gè)數(shù)字不滿足。一旦這個(gè)滿足標(biāo)準(zhǔn)數(shù)字找出來之后，另外兩個(gè)數(shù)字也就可以找出來了。

這種思路的C++代碼如下：

void getThreeUnique(vector& numbers, vector& unique)

{

if(numbers.size() < 3)

return;

int xorResult = 0;

vector::iterator iter = numbers.begin();

for(; iter != numbers.end(); ++iter)

xorResult ^= *iter;

int flags = 0;

for(iter = numbers.begin(); iter != numbers.end(); ++iter)

flags ^= lastBitOf1(xorResult ^ *iter);

flags = lastBitOf1(flags);

// get the first unique number

int first = 0;

for(iter = numbers.begin(); iter != numbers.end(); ++iter)

{

if(lastBitOf1(*iter ^ xorResult) == flags)

first ^= *iter;

}

unique.push_back(first);

// move the first unique number to the end of array

for(iter = numbers.begin(); iter != numbers.end(); ++iter)

{

if(*iter == first)

{

swap(*iter, *(numbers.end() - 1));

break;

}

}

// get the second and third unique numbers

getTwoUnique(numbers.begin(), numbers.end() - 1, unique);

}

int lastBitOf1(int number)

{

return number & ~(number - 1);

}

void getTwoUnique(vector::iterator begin, vector::iterator end, vector& unique)

{

int xorResult = 0;

for(vector::iterator iter = begin; iter != end; ++iter)

xorResult ^= *iter;

int diff = lastBitOf1(xorResult);

int first = 0;

int second = 0;

for(vector::iterator iter = begin; iter != end; ++iter)

{

if(diff & *iter)

first ^= *iter;

else

second ^= *iter;

}

unique.push_back(first);

unique.push_back(second);

}

上文中g(shù)etThreeUnique從數(shù)組中找出三個(gè)只出現(xiàn)一次的數(shù)字，而getTwoUnique從數(shù)組中找出兩個(gè)只出現(xiàn)一次的數(shù)字。lastBitOf1實(shí)現(xiàn)分析中的函數(shù)f(n)的功能，它只保留數(shù)字n的二進(jìn)制表示中的最后一位1，而把其他所有位都變成0。

在函數(shù)getThreeUnique中，我們通過第一個(gè)for循環(huán)把a(bǔ)、b、c三個(gè)數(shù)字異或的結(jié)果保存到xorResult中，接著在第二個(gè)for循環(huán)中求出f(x^a)^f(x^b)^f(x^c)并保存到變量flags中。在語句flags=lastBitOf1(flags)求出f(x^a)^f(x^b)^f(x^c)結(jié)果的二進(jìn)制中最后一位是1的位。并根據(jù)這一數(shù)位求出第一個(gè)只出現(xiàn)一次的數(shù)字first。接著把first交換到數(shù)組的最后，并在數(shù)組的前n-1個(gè)數(shù)字中求出另外兩個(gè)只出現(xiàn)一次的數(shù)字。

[程序員面試題精選100題(63)-數(shù)組中三個(gè)只出現(xiàn)一次的數(shù)字[算法]]相關(guān)文章：

1.程序員面試題精選100題(63)-數(shù)組中三個(gè)只出現(xiàn)一次的數(shù)字[算法]

2.微軟面試100題系列

【程序員面試題100題(63)-數(shù)組中三個(gè)只出現(xiàn)一次的數(shù)字[算法]】相關(guān)文章：

程序員面試題精選100題-字符串的組合[算法]07-13

程序員精選面試題100題07-13

程序員面試題-求Fibonacci數(shù)列[算法]07-13

另一道遞歸算法題（2009年企業(yè)面試題）07-13

JAVA算法面試題：哪位高人會(huì)做？07-13

淘寶面試題求解--數(shù)據(jù)挖掘-算法07-13

2014年MBA面試題目大綱100題07-11

程序員面試題精選07-12

今天參加了華為的面試，被一個(gè)算法題水了？07-11