找到一个数组中只出现一次的数

你有没有遇到这样的题，在一个数组中，只有1个数字出现一次，其他的数字都出现了两次，那么你能找到这个只出现一次的数字么？

这只是简单的1.0版本，还有如果在这个数组中，有两个数字出现了一次，其他的数字都出现了两次，那么你能找到这两个数字么？

还有2.0版本，三个数字出现一次呢？四个呢？五个呢？你要怎么去实现呢？

首先，我们一步一步来，从找一个数字开始，其实，如果不是考虑到内存的关系，用桶排序是可以很好地解决这个问题的，但是，桶排序，实在是太耗内存了。那么我们就换个思路，我们想到，在运算符中有这样一个^（异或）的符号，我们完全可以利用这个异或来实现。也许你已经想到要怎么去实现了，没错，就是这样实现的。举个例子吧，a[3] = {1,1,2},将这三个数异或一下，就可以得到2，是不是很简单？这样我们就找到了这个只出现一次的数字了。好，那我们用代码来实现吧：

#include<stdio.h>
int main()
{
	int a[] = {1,1,2,2,3,3,4,4,5};
	int sz = sizeof(a)/sizeof(a[0]);
	int i = 0;
	int x = 0;
	for(i=0;i<sz;i++)
	{
		x ^= a[i];//将所有的数与一下
	}
	printf("%d\n",x);
	return 0;
}

你也可以自己实现一下。

那么我们接下来来看两个数字均出现一次的情况吧。其实如果我们这么想，如果可以把这个数组分成两组，把这两个数字分别分到两组中去，实际上就是找一个数字了。

我们可以来看一下，如果直接将所有的数字异或在一起，得到的是什么呢？举个例子a[]={1,1,2,2,3,3,4,5},

以这个例子来看，应该是 4^5(4和5异或的结果），那我们从二进制数的角度来看一下

100//4

101//5

001//异或之后的结果

那么我们可以看到，4和5的二进制数有一位不同，我们可不可以依据这个来进行分组呢？

那么，分组的结果是：

第一组：1,1,3,3,5 ;   

第二组： 2,2,4;

在这两组中分别运用第一种方法，即可分别找到这两个数字了。

怎么实现呢？

#include<stdio.h>
int main()
{
	int a[] = {1,1,2,2,3,3,4,4,5,5,6,7};
	int i = 0;
	int sz = sizeof(a)/sizeof(a[0]);
	int n = 0;
	int pos = 0;
	int x = 0;
	int y = 0;
	for(i=0;i<sz;i++)
	{
		n ^= a[i];//将所有的数异或 得到 6^7 的结果
	}
	for(i=0;i<32;i++)
	{
		if(1 == (n>>i)&1)
		{
			pos = i;//找到 6^7 的二进制数中为1的一位
			break;
		}
	}
	for(i=0;i<sz;i++)//开始分组
	{
		if(1 == ((a[i]>>pos)&1))
		{
			x ^= a[i];//得到一个数
		}
		else
		{
			y ^= a[i];//得到另一个数
		}
	}
	printf("%d  %d\n",x,y);
	return 0;
}

你会了么？

3.0版呢以后再更新。