首页 / 软件开发 / 数据结构与算法 / 经典算法（12） 数组中只出现1次的两个数字（百度面试题）

经典算法（12） 数组中只出现1次的两个数字（百度面试题）2014-01-03 csdn MoreWindows首先来看题目要求：

在一个数组中除两个数字只出现1次外，其它数字都出现了2次， 要求尽快找 出这两个数字。

考虑下这个题目的简化版——数组中除一个数字只出现1次外，其它数字都成对出现 ，要求尽快找出这个数字。这个题目在之前的《位操作基础篇之位操作全面总结》中的“位操作趣味应用” 中就已经给出解答了。根据异或运算的特点，直接异或一次就可以找出这个数字。

现在数组中有两个 数字只出现1次，直接异或一次只能得到这两个数字的异或结果，但光从这个结果肯定无法得到这个两个数字 。因此我们来分析下简化版中“异或”解法的关键点，这个关键点也相当明显——数组只能有一个数字出现1 次。

设题目中这两个只出现1次的数字分别为A和B，如果能将A，B分开到二个数组中，那显然符合“ 异或”解法的关键点了。因此这个题目的关键点就是将A，B分开到二个数组中。由于A，B肯定是不相等的， 因此在二进制上必定有一位是不同的。根据这一位是0还是1可以将A，B分开到A组和B组。而这个数组中其它 数字要么就属于A组，要么就属于B组。再对A组和B组分别执行“异或”解法就可以得到A，B了。而要判断A， B在哪一位上不相同，只要根据A异或B的结果就可以知道了，这个结果在二进制上为1的位都说明A，B在这一 位上是不相同的。

比如int a[] = {1, 1, 3, 5, 2, 2}

整个数组异或的结果为3^5即 0x0011 ^ 0x0101 = 0x0110

对0x0110，第1位（由低向高，从0开始）就是1。因此整个数组根据第1位是0还是 1分成两组。

a[0] =1  0x0001  第一组

a[1] =1  0x0001  第一组

a[2] =3  0x0011  第二组

a[3] =5  0x0101  第一组

a[4] =2  0x0010  第二组

a[5] =2  0x0010  第二组

第一组有{1, 1, 5}，第二 组有{3, 2, 3}，明显对这二组分别执行“异或”解法就可以得到5和3了。

分析至些，相信代码不难 写出，下面给出完整的源代码：

// 百度面试题//数组中除两个数字外，其它数字都出现了次。要求尽可能快的找出这两个数字//By MoreWindows （http://blog.csdn.net/MoreWindows）#include <stdio.h>void FindTwoNotRepeatNumberInArray（int *a, int n, int *pN1, int *pN2）{int i, j, temp;//计算这两个数的异或结果temp = 0;for （i = 0; i < n; i++）temp ^= a[i];// 找第一个为1的位for （j = 0; j < sizeof（int） * 8; j++）if （（（temp >> j） & 1） == 1）break;// 第j位为1,说明这两个数字在第j位上是不相同的// 由此分组即可*pN1 = 0, *pN2 = 0;for （i = 0; i < n; i++）if （（（a[i] >> j） & 1） == 0）*pN1 ^= a[i];else*pN2 ^= a[i];}void PrintfArray（int a[], int n）{for （int i = 0; i < n; i++）printf（"%d ", a[i]）;putchar（"
"）;}int main（）{printf（"白话经典算法系列之十二数组中不重复的个数字（百度面试题） 
"）;printf（" -- by MoreWindows（ http://blog.csdn.net/MoreWindows ） --

"）; const int MAXN = 10;//int a[MAXN] = {1, 2, 7, 5, 100,100, 6, 1, 2, 5};int a[MAXN] = {1, 2, 3, 4, 1,2, 3, 4, 0, 5};printf（"数组为: 
"）;PrintfArray（a, MAXN）;int nNotRepeatNumber1, nNotRepeatNumber2;FindTwoNotRepeatNumberInArray（a, MAXN, &nNotRepeatNumber1, &nNotRepeatNumber2）;printf（"两个不重复的数字分别为: %d %d
", nNotRepeatNumber1, nNotRepeatNumber2）;return 0;}

运行结果如下所示：

百度面试在算法这一环节上一 般会出多道算法题，下次再整理几篇，欢迎大家继续参阅。

原文地址： http://blog.csdn.net/morewindows/article/details/8214003