大家无聊来做做题

YuHaiyang · 发表于 2011-10-5 17:28:56

设有很大的一堆数，共奇数个，除了1个数外，每个数出现偶数次，找出这个数，复杂度尽量小

tangzk · 发表于 2011-10-5 19:31:25

加减交替，最后的sum取abs即可。时间复杂度O(n)
另外更有全部异或，最后的结果即是所求。亦是O(n)

YuHaiyang · 发表于 2011-10-6 09:39:55

tangzk 发表于 2011-10-5 19:31
加减交替，最后的sum取abs即可。时间复杂度O(n)
另外更有全部异或，最后的结果即是所求。亦是O(n)

异或是没问题的，加减交替是？

tangzk · 发表于 2011-10-6 21:12:41

YuHaiyang 发表于 2011-10-6 09:39
异或是没问题的，加减交替是？

呀，加减交替有问题，还需要有排序操作才行。
暂时就想到异或了，还有其它高招没？

YuHaiyang · 发表于 2011-10-7 11:16:35

tangzk 发表于 2011-10-6 21:12
呀，加减交替有问题，还需要有排序操作才行。
暂时就想到异或了，还有其它高招没？

我只知道异或~