学步园

题目

题目链接：http://ac.jobdu.com/problem.php?pid=1351 ，《剑指Offer》 P211。

题目描述：一个整型数组里除了两个数字之外，其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

解题思路

看到这个题的时候，大家通常会利用比较普通的解法，先对数组排序，然后再遍历一篇，但是题目

要求时间复杂度是O(n)，空间复杂度是O(1)。

此时我们只能考虑下位运算的方法了，现在思考这个问题的一个简单版本：

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

题目为什么要强调有一个数字出现一次，其他的出现两次？

我们想到了异或运算的性质：任何一个数字异或它自己都等于0。

有了上面简单问题的解决方案之后，我们回到原始的问题。现在考虑如何把原数组分为两个子数组。

对于这个问题，还是到 海涛大神那细看他的分析http://zhedahht.blog.163.com/blog/static/2541117420071128950682/。

根据上面的解法实现自己的代码如下：

#include <stdio.h> 
#include <stdlib.h>
//p为数组集合,len 为数组长度，pn1,pn2分别为指向两个单独数的指针
void find(int *p, int len, int *pn1, int *pn2)
{
	int num = 0;
	int i;
	for(i=0; i<len; ++i)
	{
		num ^= p[i];
	}
	int offset = 1;//第一次出现1的位置,从低位开始寻找
	while(0 == (num & (1<<offset)))// 从寻低位找第一位1的位置
		offset++;
	*pn1 = 0, *pn2 = 0;
	for(i=0; i < len; i++)
		if(p[i] &(1<<offset))// 根据offset位是否为1把数组分为2个数组
			*pn1 ^= p[i];//*pn1 异或一个数组，最后得到第一单独出现的数
		else
			*pn2 ^= p[i];//同理*pn1
}


int main() 
{
	int n, num1, num2;
	int *p;

	while(EOF != scanf("%d", &n))
	{
		p = (int *)malloc(n*sizeof(int));
		for(int i=0; i<n; i++)
		{
			scanf("%d", p+i);
		}
		find(p, n, &num1, &num2);
		if(num1<num2)
			printf("%d %d\n", num1, num2);
		else
			printf("%d %d\n", num2, num1);
		free(p);
	}
	return 0;
}