快速找出奇数次数的数

wayne

我先说一下我的笨方法， 我的方法没有利用到“唯一”， 而是找出了所有的出现奇数次的元素： 设原数组为A, 先建立一个同大小的数组B和C，分别用来存A中互异的元素及其对应的计数。B初始化为A中的第一个元素，C初始化为1. 从A的第二个元素开始遍历，对A中每一个元素，遍历数组B，判断，如果A在数组B中，则对应索引的C元素增1；如果不在B中，则B后面追加该A中的元素，C后面追加一元素，值为1. A遍历完后，对数组C遍历，判断奇偶，找出奇数对应的索引，于是在B中提取出来

gxqcn

楼上的方法与 3# 的相近。 但 风云剑 采用了 STL 的 map 容器，其实用一个 set 即可。 遍历时，有则删除，无则新增。最后留下的极为所求。 这样不仅可以减少空间消耗，而且容器的大小会动态缩放，可以减少每次查询的代价。

wayne

学过C，但没看到有容器和的概念，不知道这道题用纯C来写，会依赖什么库。。。 如果允许用其他语言，或许一个只有五个字符的函数就可以直接搞定。 我也很想知道，抛开程序语言的那些技术细节，在数学上，有没有什么算法上的亮点。 media2005说的异或，我还没看懂。

gxqcn

这题就是充分利用异或具有交换律和结合率的特性。 比如有：a XOR b XOR c = b XOR a XOR a = b XOR ( a XOR a ) = b XOR 在 C 里就是“^”运算符，不依赖第三方库，也无需新写函数。

风云剑

自己和自己异或结果等于0。 所以偶数个的全成了0，奇数个的最后剩一个 set是什么容器？不太熟悉，呵呵。

gxqcn

map 是种映射，set 是集合。 前者需要存key和value，后者仅需存key即可。 用的都是红黑树算法。

kon3155

其实，我在帖子题目里已把重点给突出来了。 ls 肯定早就知晓答案了。 请问：2# 的第2问解决方法是否与第1问类似？可有关联？ gxqcn 发表于 2009-9-28 12:30

2楼给出的是《编程之美》1.5节中《快速找出故障机器》的题目 对于第二种情况，即列表中缺少两个不等的ID，只通过异或运算是无法直接得到结果的。但根据异或结果可以得到下面这个信息： 若结果中二进制中的某位为1，则表示缺少的两个ID二进制在该位置上的位不同， 即一个为1另一个为0；下面的问题就是如何找到这2个ID了。 《编程之美》中的解法是将ID列表中的ID在异或运算结果为1的位上分为两组，一组ID在该位置上的位为1，另一组在该位置上为0；这样再将两组分别作异或运算即可得出缺少的两个ID的值。 另外，如果ID列表事先已知的话，还有更简单易懂的方法来求2台故障机器的ID。

Frankenstein

建一个专门记录的表，一个一个的读入，遇到了相同的数字就消了最后就只会剩下一个数就是答案。 在最坏的情况下占内存为 （总的个数-3）/2+1，如果不是特别坏的话，均匀分布的话就只会占比较少的内存。 我的方法是不是很慢啊？好像“遇到相同数字”也要遍历一次新建的表，希望看到更快的

knate

随机取x截成数组两组ak,bk ak均不大于x,bk 大于x ak.bk有且只有一个是size()为奇数, 所求元素必然在size()为奇数处. 如此反复即可. 如果数据无序复杂度为n 如果数据有序复杂度为logn

knate

修正 如果数据有序复杂度为klogn ////k为最多重复次数.