[各种面试题] 找出三个只出现一次的数

2017年12月23日 ⁄ 综合 ⁄ 共 2455字 ⁄ 字号 评论关闭

```void getThreeUnique(vector<int>& numbers, vector<int>& unique)
{
if(numbers.size() < 3)
return;

int xorResult = 0;
vector<int>::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<int>::iterator begin, vector<int>::iterator end, vector<int>& unique)
{
int xorResult = 0;
for(vector<int>::iterator iter = begin; iter != end; ++iter)
xorResult ^= *iter;

int diff = lastBitOf1(xorResult);

int first = 0;
int second = 0;

for(vector<int>::iterator iter = begin; iter != end; ++iter)
{
if(diff & *iter)
first ^= *iter;
else
second ^= *iter;
}

unique.push_back(first);
unique.push_back(second);
}```