Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1864390
  • 博文数量: 283
  • 博客积分: 10141
  • 博客等级: 上将
  • 技术积分: 2931
  • 用 户 组: 普通用户
  • 注册时间: 2005-12-21 14:33
文章分类

全部博文(283)

文章存档

2013年(2)

2012年(2)

2011年(17)

2010年(36)

2009年(17)

2008年(18)

2007年(66)

2006年(105)

2005年(20)

分类: C/C++

2007-11-22 10:09:58

发信人: jtuer (吉天游人), 信区: Algorithm
标  题: 来看一个microstrategy的笔试题。。。
发信站: 水木社区 (Wed Nov 21 19:05:10 2007), 站内

奇数个整数,其中只有一个整数重复奇数次,其他的重复偶数次。找出奇数次的整数

一些思路:
1. 假设有N个整数,申请一个数组A,scan这N个整数Xi,如果A中没有Xi,加入,有则删除,最后A中剩下的就是所求。这个,数组A如果大小为(N+1)/2(最大情况),那么每次都scan,差不多O(N^2)了 -_-b
2. 排序,然后去数出现次数O(Nlg(N))

提示:
考虑异或的特性...a^a^b=b

解:
O(N)阶,只需要把N个数异或一次即可得答案。

阅读(2805) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~