microstrategy笔试一道(源于水木社区)
(2007-11-22 10:09)
分类： Career
发信人: 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个数异或一次即可得答案。