程序员面试题精选100题（63）-数组中三个只出现一次的数字

程序员面试题精选100题(63)-数组中三个只出现一次的数字

       在将这个题目之前，先讲讲一个数组中有两个数字出现一次，其他的都出现两次的情况。具体题目如下：

     题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

分析：首先考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。这个题目的突破口在哪里？题目为什么要强调有一个数字出现一次，其他的出现两次？想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字，因为那些出现两次的数字全部在异或中抵消掉了。

有了上面简单问题的解决方案之后，回到原始的问题。如果能够把原数组分为两个子数组，在每个子数组中，包含一个只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办法就是分别求出这两个只出现一次的数字了。

还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次，在异或中全部抵消掉了。由于这两个数字肯定不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1。在结果数字中找到第一个为1的位的位置，记为第N位。现在以第N位是不是1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N位都为1，而第二个子数组的每个数字的第N位都为0。

现在已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。因此到此为止，所有的问题都已经解决。

测试代码如下：

#include<iostream>
using namespace std;

unsigned int FindFirstBitIs1(int num)
{
  int indexBit=0;
  while(((num&1)==0) &&(indexBit<32))
  {
    num=num>>1;
++indexBit;
  }
  return indexBit;
}

bool IsBit1(int num,unsigned int indexBit)
{
  num=num>>indexBit;
  return (num&1);
}

void FindNumsAppearOnce(int data[],int length,int &num1,int &num2)
{
  if(length<2)
 return;
  int resultExclusiveOR=0;
  for(int i=0;i<length;i++)
 resultExclusiveOR^=data[i];
  unsigned int indexOf1=FindFirstBitIs1(resultExclusiveOR);
  num1=num2=0;
  for(int j=0;j<length;j++)
  {
    if(IsBit1(data[j],indexOf1))
num1^=data[j];
else
num2^=data[j];
  }
}

int main()
{
int a[8]={2,3,6,8,3,2,7,7};
int x,y;
FindNumsAppearOnce(a,8,x,y);
cout<<x<<" "<<y<<endl;
return 0;
}


    下面讲解一个数组中出现三个只出现一次的数字，这个题目其实和上面类似。具体的题目与分析如下：

      题目：一个整型数组里有三个数字出现了一次，其他的数字都出现了两次。请写程序找出这3个只出现一次的数字。

分析：思路类似于上题，关键是找出第一个来，然后借助上题结论求另外两个。

假设x y z为只出现一次的数，其他出现偶数次。lowbit为某个数从右往左扫描第一次出现1的位置，则x^y、 x^z、 y^z 这三个值的lowbit有一个规律，其中肯定两个是一样的，另外一个是不一样的。令flips为上述三个值的异或，即flips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)。因此，可以利用此条件获得某个x(或者y，或者z)，循环判断的条件是a[i]^xors的lowbit==flips（其中xors为所有数的异或值）
解释：a[i]^xors即可划分为两组，一组是lowbit与flips不同，一组是lowbit与flips相同。这样就能找到某个x,y,z，找出后，将其与数组最后一个值交换，在利用上题思路，在前面n-1个数中找出剩余两个。
    具体的代码实现：

#include<iostream>
using namespace std;

int lowbit(int x)
{
  return x&~(x-1);
}

void Find2(int seq[],int n,int& a,int& b)
{
  int xors=0;
  for(int i=0;i<n;i++)
 xors^=seq[i];
  int diff=lowbit(xors);
  for(int j=0;j<n;j++)
  {
    if(diff & seq[j]) //与运算，表示数组中与异或结果位为1的位数相同
a^=seq[j];
else
b^=seq[j];
  }
}
//三个数两两的异或后lowbit有两个相同，一个不同，可以分为两组
void Find3(int seq[],int n,int &a,int &b,int &c)
{
  int i,xors=0;
  for(i=0;i<n;i++)
 xors^=seq[i];
  int flips=0;
  for(i=0;i<n;i++) //因为出现偶数次的seq[i]和xors的异或，异或结果不改变
 flips^=lowbit(xors^seq[i]); //表示的是：flips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)
  //三个数两两异或后lowbit有两个相同，一个不同，可以分为两组
  //所以flips的值为：lowbit(a^b)或lowbit(a^c)或lowbit(b^c)
  //得到三个数中的一个
  a=0;
  for(i=0;i<n;i++)
  {
    if(lowbit(seq[i]^xors)==flips) //找到三个数两两异或后的lowbit与另外两个lowbit不同的那个数。
a^=seq[i];
  }
  //找出后，与数组中最后一个值交换，利用Find2找出剩余的两个。
  for(i=0;i<n;i++)
  {
    if(a==seq[i])
{
 int temp=seq[i];
 seq[i]=seq[n-1];
 seq[n-1]=temp;
}
  }
  //利用Find2，找出剩余的两个
  Find2(seq,n-1,b,c);
}

int main(void)
{
int seq[]={2,3,3,2,4,6,4,10,9,8,8};
int a=0,b=0,c=0;
Find3(seq,11,a,b,c);
cout<<a<<endl;
cout<<b<<endl;
cout<<c<<endl;
return 0;
}