欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-13 14:57:41
...

你有没有遇到这样的题,在一个数组中,只有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版呢以后再更新。