快速找出奇数次数的数

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

感觉想脑筋急转弯哦