kk Blog —— 通用基础

problem

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

answer

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

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