快速找出奇数次数的数

gxqcn

为活跃气氛，给大家出一道比较简单的算法题。欢迎大家也来出一些小巧的算法题。 古有云：数有奇偶，奇数为阳，偶数为阴。 今天我们要说的不是数的奇偶，而是数字重复次数的奇偶。 说的是： 有一个由很多整数构成的数组，但其元素多有重复，重复次数不尽相同。 比较奇特的是，重复次数最多的为一个奇数，其余的次数均为偶数（零恰巧也属于偶数之列）。 现在，请设计一个尽可能快的算法，找出这个出现奇数次的整数。 比如：1、4、5、4、5、4、5、5、4、1、4，结果应为“4” 上述题目中有些信息是冗余的，如果点破了则显得非常简单。 确信得到答案者最好将回帖设置成“回复可见”，以便给其他网友留有思考空间。

kon3155

一个实际应用： 有很多服务器存储数据，假设一个机器仅存储一个标号为ID的记录，假设机器总量在10亿以下且ID是小于10亿的整数，假设每份数据保存两个备份，这样就有两个机器存储了同样的数据。 问题是：1.假设在某个时间得到一个数据文件ID的列表，是否能快速地找出表中仅出现一次的ID？ 即快速找出出现故障的机器存储的数据ID。 2.如果有两台机器出现故障呢？（假设存储同一份数据的两台机器不会同时出现故障， 即列表中缺少的是两个不等的ID）

风云剑

还真想不出什么快速的方法，再怎么说也要遍历一遍吧。一个变量记录最大值，初始化为0，建一个大数组，初始化为0，将遍历到的数值作为下标，遍历一个，相应的数组项加1，同时和最大值比较，记录。最后就得到了。当然，建的大数组可能会巨型了，呵呵。实际中，用STL的map也许是个办法。

gxqcn

上面的算法时间和空间耗费都太大，不适合。 可以有一个算法，额外只用极小的空间，遍历一遍即可得到结果，大家再想想。。。

wayne

就那一个数是奇数次吗， 是不是遍历求和做标记来判断奇偶

medie2005

游客，如果您要查看本帖隐藏内容请回复

wayne

虽说2楼给出了实际应用， 但我总感觉这题挺怪异的， 看来我根本就是不在行啊，

gxqcn

其实你很厉害的。 怪我故意在题目中新增了一些无用的干扰信息，让人抓不住重点。

kon3155

快速找出数组中唯一一个出现奇数次的数！其他的都是干扰信息。

gxqcn

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