找唯一重复的元素

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。

 

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

  1. coder4digiter

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

    Reply
  2. coder4digiter

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

    Reply

Leave a Reply

Your email address will not be published.