kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

两个数只出现一次

problem

一个数组,其中只有两个数只出现一次,其余数皆出现偶数次。
设计Time: O(n) 的算法得出那个只出现一次的数。

answer

再因为a和b不等,那么ab必然不为0。
那么ab这个数上面必然能够找到一个二进制位是1
在这个二进制位上,a和b不等。
根据这个二进制位,将各元素中在这位上为1的分派到左边,为0的分派到右边,形成两个子数组。

可以证明,
1)这两个数组分别包含a和b。
2)每个数组中除了a或b之外的所有元素都是成对出现的。