转载请注明出处:http://blog.csdn.net/mmc_maodun/article/details/27800577
题目：一个int数组中有三个数字a、b、c只出现一次，其他数字都出现了两次。请找出三个只出现一次的数字。
上篇博文中我们求的是两个只出现一次的数字，且时间复杂度为O(n)，这次是三个，可以同样考虑将数组先分成两个子数组，求出其中一个只出现一次的数字，而后再将另一个子数组分成两个子数组，再分别求这两个只出现一次的数字。何海涛的博客给的就是这种思路，并给出了详细的证明过程，详见：http://zhedahht.blog.163.com/blog/static/25411174201283084246412/，但该方法真的要自己去想，很难想到，而且如果是面试的话，很难给面试官讲懂。下面介绍另外一种方法，该方法具一定的通用性，对于2个，3个出现一次的数字这类的问题，都可以按照该思路去求解，只是时间复杂度可能要稍微大些，为O(8*sizeof(int)*n)，8*sizeof(int)其实即使int的位，在一般的32位系统中，它为32，而n自然就是数组的长度了。
该方法的思路如下：
首先由于有3个数字出现一次，其他的都出现两次，所以n肯定为奇数，该方法通过扫描整数的每一位来逐个判断。
再看这3个只出现一次的数字，他们的bit位肯定不可能全部相同，也就是说，虽然有些bit位上的数可能相等，但肯定至少存在某一个bit位，这三个数中，有两个数的该bit位为1，一个数的该bit位为0，或者两个数的该bit位为0，一个数的该bit位为1。我们可以通过扫面int的所有bit位，扫描每个bit位的时候，遍历数组，如果能找出符合上面条件的，我们就可以找出其中的一个只出现一次的数字，该数字与另外两个只出现一次的数的bit位不同。找到一个之后，就可以将其与数组的最后一个元素交换，再在前面n-1个数中找出另外两个就可以了，方法的话，可以直接用上篇博文中介绍的方法，也可以用该博文介绍的思路。
下面要来看下如果找出这个与另外两个数的该bit位不同的数。
先看第一种情况，如果a，b，c三个数中，有两个该bit位为0，另一个为1，我们遍历数组，分别统计该数组元素中该bit位为1和0的元素个数，分别设为count1和count0，并同时将所有该bit位为1的元素异或，所有该bit位为0的元素异或，得到的结果分别设为temp1和temp0。如果count1为奇数，则可能有两种情况，a，b，c三个数的该bit位全为1，或者有两个为0，一个为1，如果有temp0==0,则说明是前一种情况（a，b，c的该bit位全为1的话，所有该bit位为0的每个元素出现了两次，因此异或后的结果为0），此时没法找出其中的一个数，则直接跳到下次循环，继续判断下一个bit位，如果temp0！=0，则说明是后一种情况（说明该比bt位为0的元素异或后没有完全抵消，则说明有一个元素是只出现一次的），此时其中一个只出现一次的数字就是temp0（重复的元素异或后都抵消了）。
第二种情况，是两个该bit位为1，另一个为0的情况，分析思路与上面的类似。
很明显，这种扫描每个bit位来进行判断的思路可以解决整个的这一类问题，自然也可以求出上篇博文中两个只出现一次的数字。具体思路不再给出，主要的判断依据，一般都是bit位为1或0的数字的个数的奇偶，bit位为1的元素异或，bit位为0的元素异或后的结果是否为0的判断。
下面给出这道题目的完整代码：
#include<stdio.h>测试结果：
/*
通过扫面每一位，先找出一个只出现一次的数
*/
int FindOneNumAppearOnce(int *arr,int len)
{
int count1 = 0;//某一位上1的个数
int count0 = 0; //某一位上0的个数
int temp1 = 0;//某一位为1的所有数相异或的结果
int temp0 = 0;//某一位为0的所有数相异或的结果
int i,j;
for(i=0;i<8*sizeof(int);i++)//循环计算每一位的以上四个数据
{
count1 = count0 = temp1 = temp0 = 0;//每次计算下一位时清零
for(j=0;j<len;j++)
{
//每次向左移一位进行计算
if(arr[j] & (1<<i))//该位为1时
{
temp1 ^= arr[j];
count1++;
}
else
{
temp0 ^= arr[j];
count0++;
}
}
if(temp1 & 1)//某位上有奇数个1
{
if(temp0 == 0)//此时3个不同数的该位都为1
continue;
else//此时3个不同数的该位有1个1，2个0
return temp1;
}
else//某位上有偶数个1
{
if(temp1 == 0)//此时3个不同数的该位都为0
continue;
else//此时3个不同数的该位有1个0，2个1
return temp0;
}
}
}
/*
返回num的最低位的1，其他各位都为0
*/
int FindFirstBit1(int num)
{
//二者与后得到的数，将num最右边的1保留下来，其他位的全部置为了0
return num & (-num);
}
/*
判断data中特定的位是否为1，
这里的要判断的特定的位由res确定，
res中只有一位为1，其他位均为0，由FindFirstBit1函数返回，
而data中要判断的位便是res中这唯一的1所在的位
*/
bool IsBit1(int data,int res)
{
return ((data&res)==0) ? false:true;
}
void FindTwoNumsAppearOnce(int *arr,int len,int *num1,int *num2)
{
int i;
int AllXOR = 0;
//全部异或
for(i=0;i<len;i++)
AllXOR ^= arr[i];
int res = FindFirstBit1(AllXOR);
*num1 = *num2 = 0;
for(i=0;i<len;i++)
{
if(IsBit1(arr[i],res))
*num1 ^= arr[i];
else
*num2 ^= arr[i];
}
}
/*
交换两个int变量
*/
void Swap(int *a,int *b)
{
if(*a != *b)
{
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
}
/*
找出这三个只出现一次的数字
*/
void FindThreeNumsAppearOnce(int *arr,int len,int *num1,int *num2,int *num3)
{
if(arr==NULL || len<3)
return;
*num1 = FindOneNumAppearOnce(arr,len);
//找到第一个找出的数字，并与最后一个元素交换，便于接下来剩下的两个数字
int i;
for(i=0;i<len;i++)
if(*num1 == arr[i])
break;
Swap(&arr[i],&arr[len-1]);
FindTwoNumsAppearOnce(arr,len-1,num2,num3);
}
int main()
{
static int arr[1000000];
int n;
while(scanf("%d",&n) != EOF)
{
int i;
for(i=0;i<n;i++)
scanf("%d",arr+i);
int num1,num2,num3;
FindThreeNumsAppearOnce(arr,n,&num1,&num2,&num3);
printf("%d %d %d\n",num1,num2,num3);
}
return 0;
}
