找唯一重复的元素

1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?

普通青年解法:

1+2+....+1000->5050

a1+a2+....+a1001->X

x - 5050 -> n(重复)

文艺青年解法:

a1^a2^.....a1001 = n(对所有的元素求一遍异或,就是最终重复的元素)

证明也不复杂,见:

http://www.cnblogs.com/Ivony/archive/2009/07/23/1529254.html

补充:

1、有N+1个数,N个数出现了偶数次,1个数出现了奇数次,问用O(1)的空间复杂度,找出这两个数。

看了证明就知道,和上面的做法一样,依然是a1^a2^.....a1001 = 数字n,因为偶数次异或抵消

2、有N+2个数,N个数出现了偶数次,2个数出现了奇数次(这两个数不相等),问用O(1)的空间复杂度,找出这两个数。

参考:http://blog.csdn.net/wodewe/article/details/6863753

假设这两个数为a,b,将数组中所有元素异或结果x=a^b,判断x中位为1的位数(注:因为a!=b,所以x!=0,我们只需知道某一个位为1的位数k,例如0010 1100,我们可取k=2或者3,或者5),然后将x与数组中第k位为1的数进行异或,异或结果就是a,b中一个,然后用x异或,就可以求出另外一个。

为什么呢?因为x中第k位为1表示a或b中有一个数的第k位也为1,假设为a,我们将x与数组中第k位为1的数进行异或时,也即将x与a外加其他第k位为1的出现过偶数次的数进行异或,化简即为x与a异或,结果是b。

void getNum(int a[],int length)
{
	int s=0;//保存异或结果
	for(int i=0;i<length;i++)
	{
		s=s^a[i];
	}
	int temp1=s;//临时保存异或结果
	int temp2=s;//临时保存异或结果
	int k=0;
	while(!(temp1&1))//求位为1的位数
	{
		temp1=temp1>>1;
		k++;
	}
	for(int i=0;i<length;i++)
	{
		if((a[i]>>k)&1)//将s与数组中第k位为1的数异或
		{
			cout<<a[i]<<" ";
			s=s^a[i];
		}
	}
	cout<<s<<" "<<(s^temp2)<<endl;//(s^temp2)用来求另外一个数
}

 

2 thoughts on “找唯一重复的元素

  1. digiter

    这是经典面试题了,再一般化点儿就是一个元素出现奇数次,其他都是偶数次
    再变复杂点可以是有两个元素出现奇数次,其他偶数次,找出这两个元素,呵呵~

    Reply
  2. digiter

    这是经典面试题了,再一般化点儿就是一个元素出现奇数次,其他都是偶数次再变复杂点可以是有两个元素出现奇数次,其他偶数次,找出这两个元素,呵呵~

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *