題目描述：
Given an array of n integers, such that each number in the array appears exactly twice, except for three numbers (say a, b and c) which appear exactly once.
In O(n) time and O(1) space find a,b and c.
分析：
先看這樣一道題：
n個(gè)數(shù)中有且僅有一個(gè)數(shù)出現(xiàn)了奇數(shù)次（其它數(shù)都出現(xiàn)了偶數(shù)次），如何用線性時(shí)間常數(shù)空間找出這個(gè)數(shù)。
解法如下：
從頭到尾異或一遍，結(jié)果就是要求的那個(gè)數(shù)。（原理很清楚明了）
再看稍微加強(qiáng)版：
n個(gè)數(shù)中有且僅有兩個(gè)數(shù)出現(xiàn)了奇數(shù)次（其它數(shù)都出現(xiàn)了偶數(shù)次），如何用線性時(shí)間常數(shù)空間找出這個(gè)數(shù)。
解法比較巧妙，主要思想是將元素分成兩組，每組中有且僅有一個(gè)數(shù)出現(xiàn)了奇數(shù)次（其它數(shù)都出現(xiàn)了偶數(shù)次），然后應(yīng)用上題的結(jié)論解答，至于如何分組，見下：
1、異或所有元素得xors
2、找出xors中不為0的一個(gè)bit位（通常從右向左找出第一個(gè)不為0的）
3、以2中找到的bit位為sentinel，將數(shù)組分為兩組
本題：
思路類似于求解上題，關(guān)鍵是找出第一個(gè)來，然后借助上題結(jié)論求另外兩個(gè)
// Let s = a ^ b ^ c.? We know that s not in (a, b, c),
// since if s == a, say, then b ^ c == 0 and b == c.?
// Let f(x) be the lowest bit where x differs from s.?
// The algorithm computes flips = f(a) ^ f(b) ^ f(c),
// since the numbers appearing an even number of times cancel.?
// The variable flips has parity 1, so it is non-zero,
// and lowbit(flips) is a bit where one or three of a, b, c
// differ from s.? It can't be three, however, so the final
// exclusive-or includes exactly one of a, b, c.
代碼：
#include <iostream>
using namespace std;
// get lowest different bit
int lowbit(int x)
{
??? return x & ~(x - 1);
}
// Given an array of n integers, such that each number
// in the array appears exactly twice, except for two
// numbers (say a and b) which appear exactly once.
//
// In O(n) time and O(1) space find a and b.
// e.g.
// { 2 3 3 2 4 6 4 7 8 8 }? ---> a/b = { 6 7}
void Find2(int seq[], int n, int& a, int& b)
{
??? ////XOR
??? int xors = 0;
??? for(int i = 0; i < n; i++)
??????? xors ^= seq[i];
??? ////get different bit
??? int diff = lowbit(xors);
??? ////
??? a = 0;
??? b = 0;
??? for(int i = 0; i < n; i++)
??? {
??????? if(diff & seq[i])
??????????? a ^= seq[i];
??????? else
??????????? b ^= seq[i];
??? }
}
// Given an array of n integers, such that each number
// in the array appears exactly twice, except for three
// numbers (say a, b and c) which appear exactly once.
//
// In O(n) time and O(1) space find a,b and c.
// e.g.
// { 2 3 3 2 4 6 4 7 8 8 1 }? ---> a/b = { 6 7 1}
// Let s = a ^ b ^ c.? We know that s not in (a, b, c),
// since if s == a, say, then b ^ c == 0 and b == c.?
// Let f(x) be the lowest bit where x differs from s.?
// The algorithm computes flips = f(a) ^ f(b) ^ f(c),
// since the numbers appearing an even number of times cancel.?
// The variable flips has parity 1, so it is non-zero,
// and lowbit(flips) is a bit where one or three of a, b, c
// differ from s.? It can't be three, however, so the final
// exclusive-or includes exactly one of a, b, c.
void Find3(int seq[], int n, int& a, int& b, int& c)
{
??? ////XOR
??? int xors = 0;
??? for(int i = 0; i < n; i++)
??????? xors ^= seq[i];
??? ////
??? int flips = 0;
??? for(int i = 0; i < n; i++)
??????? flips ^= lowbit(xors ^ seq[i]);
??? flips = lowbit(flips);
??? ////get one of three
??? a = 0;
??? for(int i = 0; i < n; i++)
??? {
??????? if(lowbit(seq[i] ^ xors) == flips)
??????????? a ^= seq[i];
??? }
??? ////swap a with the last element of seq
??? for(int i = 0; i < n; i++)
??? {
??????? if(a == seq[i])
??????? {
??????????? int temp = seq[i];
??????????? seq[i] = seq[n - 1];
??????????? seq[n - 1] = temp;
??????? }
??? }
??? ////call Find2() to get b and c
??? Find2(seq, n - 1, b, c);
}
int _tmain(int argc, _TCHAR* argv[])
{
??? int a,b,c;
??? int test1[] = { 2, 3, 3, 2, 4, 6, 4, 7, 8, 8 };
??? Find2(test1, 10, a, b);
??? cout<<"a = "<<a<<" , b = "<<b<<endl;
??? int test2[] = {1 , 2 , 3 };//{ 2, 3, 3, 2, 4, 6, 4, 7, 8, 8, 1 };
??? Find3(test2, 3, a, b, c);
??? cout<<"a = "<<a<<" , b = "<<b<<" , c = "<<c<<endl;
??? system("pause");
??? return 0;
}
?
本文來自CSDN博客，轉(zhuǎn)載請標(biāo)明出處：http://blog.csdn.net/yysdsyl/archive/2009/06/22/4289828.aspx