最新消息:点击查看大S的省钱秘笈

找出N个数字中唯一出现奇数次的数

编程相关 Slyar 237浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

09-12-05网络赛的一道题,用到了异或运算的几个性质。

Description

现在有n个数,只有一个数出现奇数次,把它找出来。

Input

首先一个T表示有T组数据。
每组数据一个n表示有(n<=100000)个数。
接下来n个数字a0,a1……an-1( ai在int型范围内)。

Output

输出那个出现奇数次的数。

Sample Input

2
3
2 2 100000000
5
1 2 2 2 2

Sample Output

100000000
1

Slyar:暴力会超时,不说了。更简单的办法是用异或运算的几个性质:

1、A xor A = 0,也就是说异或同一个数偶数次,结果不变。

2、异或运算满足交换律。

这样我们只需要按顺序把所有的数依次异或一遍,剩下的就是唯一出现奇数次的那个数了。更复杂的一个问题是有2个数字出现奇数次,这样异或一遍会得到那2个数异或的结果,找出2个数二进制中不同的一位,然后把所有这n个数按照在那一位是0还是1分成两类,然后对每一类分别使用前一个问题的算法即可。

转载请注明:Slyar Home » 找出N个数字中唯一出现奇数次的数

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (7)

  1. 同学,麻烦问一下,为什么我在学校的网站上运行时它说内存不够啊?
    双儿6年前 (2010-10-23)回复
  2. 厉害··· 膜拜完 学着写···
    喳喳辉7年前 (2009-12-10)回复
  3. @Slyar 额...知道了~~
    ljf7年前 (2009-12-09)回复
  4. @ljf 唔,是我们校内的,外网应该看不到...
    Slyar7年前 (2009-12-08)回复
  5. sylar,冒昧的问一下,这是哪的网络赛题目,我想试一下~~~,谢了~~
    ljf7年前 (2009-12-08)回复
  6. @felix021 哎?2个也有O(n)的?这个可能精确算出来么...我先考虑考虑...
    Slyar7年前 (2009-12-07)回复
  7. 推荐WOJ 1202,1203,1204 另,如果出现奇数次的是两个不同数,也有O(N)算法的,hoho。
    felix0217年前 (2009-12-07)回复