数组中只出现一次的数目字
数组中只出现一次的数字
- 题目描述：
- 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
- 输入：
-
每个测试案例包括两行：第一行包含一个整数n，表示数组大小。2<=n <= 10^6。第二行包含n个整数，表示数组元素，元素均为int。
- 输出：
- 对应每个测试案例，输出数组中只出现一次的两个数。输出的数字从小到大的顺序。
- 样例输入：
-
8 2 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 1000001 using 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 ****************************************************************/