快速找出奇数次数的数

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为最多重复次数.