发信人: 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) |