快速找出奇数次数的数

winxos

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

winxos

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

异或的方法确实很巧妙，不过异或跟我ls的统计速度应该差不多吧？ ++ 运算应该比 ^ 还要快一点？

gxqcn

相反，我认为 ^ 绝不比 ++ 慢（用汇编时，我比较喜欢用 xor 指令，替代 sub/add 指令）。 况且，要进行数组元素的索引，效率肯定比直接变量要慢一拍的。 还有，这里是一大批整数，每个数可以很大（可以是多位数），要统计的是数重复次数，而非单个位上的数字。

winxos

相反，我认为 ^ 绝不比 ++ 慢（用汇编时，我比较喜欢用 xor 指令，替代 sub/add 指令）。 况且，要进行数组元素的索引，效率肯定比直接变量要慢一拍的。 还有，这里是一大批整数，每个数可以很大（可以是多位数 ... gxqcn 发表于 2009-9-29 10:04

哦，我理解错题目意思了，以为都是一位的呢。但是如果是多位数的话，仍然要不同数字那么多内存啊，具体的异或代码是如何执行的呢？数组？下标如何换算呢？

gxqcn

令一个变量初始化为0， 然后与数组中的数 ^= 运算一遍， 所得的最终结果即为所求。 遍历一遍即可，无须另开数组。 上述算法还有一个优点，可以任意分割任务进行并行处理。

winxos

25# gxqcn 哦，关键是 重复次数最多的为一个奇数，其余的次数均为偶数 这个条件好苛刻，没看到其余都是偶数。

1.618

抛砖引玉下: #python代码 a = raw_input().split(',') dist = {} for x in a: if x not in dist.keys(): dist[x] = True else: dist[x]^= True print dist

wayne

呵呵，要是用Mathematica的话，只需一个函数：Commonest

kungfucop

dame it

keeya0416

感觉想脑筋急转弯哦