数组中只出现一次的数字

题目描述：

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

输入：

每个测试案例包括两行：第一行包含一个整数n，表示数组大小。2<=n <= 10^6。第二行包含n个整数，表示数组元素，元素均为int。

输出：

对应每个测试案例，输出数组中只出现一次的两个数。输出的数字从小到大的顺序。

样例输入：

82 4 3 6 3 2 5 5

样例输出：

4 6

http://ac.jobdu.com/problem.php?cid=1039&pid=22

扩展：寻找数组中只出现一次的三个数。

解题思想：

先看一个简单的实例，若是找数组中只出现一次的一个数，其它的数都出现两次，直接对数组元素进行位异或就可以得到数组中只出现一次的一个数。本题中，找数组中只出现一次的两个数，则要将数组分成2个子数组，每个子数组中仅存在出现一次的一个数。关键就在于分组的标准，而对数组中所有的元素进行异或，得到的是这个数的异或。这个结果不为0，则一定存在某一个数字的一位为1，另一个数字中的某位为0，这样异或的结果才不为0。因此分组的标准是对数组元素全部进行异或的结果中首位为1的那一位（假设是第N位）。然后以这个数与数组中元素进行与运算，进行分组。数组元素第N位为1的分一组，为0为另一组。在每个子数组中进行全部异或，最终可以得出数组中只出现一次的两个数。

代码如下：

#include <iostream>#include <cstdio>#define MAX 1000001using namespace std; int shuzu[MAX];int main(){    int n,i;        while (scanf("%d",&n)!=EOF)    {        int result = 0;        for (i=0;i<n;i++)        {            scanf("%d",shuzu+i);            result^=shuzu[i];        }        int t;        for (t=1;t<=result;t<<=1)        {            if (t&result)                break;        }        int a=0,b=0;        for (i=0;i<n;i++)        {            if (t&shuzu[i])                a^=shuzu[i];            else                b^=shuzu[i];        }        a<b?printf("%d %d\n",a,b):printf("%d %d\n",b,a);    }    return 0;}/**************************************************************    Problem: 1351    User: hnuzengchao    Language: C++    Result: Accepted    Time:920 ms    Memory:5416 kb****************************************************************/