以下是引用beyondyf在2012-3-13 19:44:25的发言:
呵呵,确实很巧妙。首先仍是获得这两个奇次出现的数(设为A和B吧,方便下面的叙述)的异或值ans。
下一步有意思,找到A和B不同的一位P。这个很重要。因为A和B在这一位上各出现奇数次,而A、B是不相等的。所以这一位1只属于其中一个,不会A、B同时在这一位上为1。其它出现偶数次的数不需要考虑,在之后的异或中会被抵消掉。
之后将这一位为1的数异或在一起为ans1,这一位为0的数异或在一起ans2。这样就将两个出现奇数次的数分离到了两个集合里。
ans1、ans2里各包含一个出现奇次的数。异或后的数就是这两个了。
确实不错。关于这个不同位的找法小曹是从高到低找的。也可以从低到高找,这都无所谓,找到一个在ans中为1的位那必然是A、B互不相同的位。
纠正一下BianChengNan。这里的数可以是任何类型的数,float、double并不影响这一算法的应用。原因,只要是二进制的数就可以,而计算机里有什么数不是二进制的呢?
我再好好想想哈,好像有道理。归为01什么都一样了,不用去考虑他是怎么存储的
,但是我还是要好好想想