题解 | #数组中只出现一次的两个数字#
数组中只出现一次的两个数字
http://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8
位运算
异或:相同为 0,不同为 1
-
首先用 sum 记录所有数异或的结果,sum 初始值为 0。因为数组中除了只出现一次的数其他都是出现两次的数,那么异或之后的结果就是只出现一次的两个数字的异或结果,即 sum = x ^ y。
-
因为 x != y 那么 sum 必不为 0,所以必然可以在 sum 的二进制表示中找到最后一个 1,然后按照 sum 的二进制数的最后一个 1 所在的位置是 1 还是 0 为划分条件,将数组中所有的数分为两组(1)是 1 的(2)是 0 的,而 x 和 y 必然不在一个分组,对于每个相同的数肯定在一个分组
-
将分组(1) 的所有数进行或运算,得到一个结果假设是 x,那么另一个数就是 y = sum ^ x
格力公司福利 356人发布
查看8道真题和解析