好用的算法技巧6、找出两个没有重复的数

6、找出两个没有重复的数

对于第一题【找出没有重复的数】

给你一组整型数据，这些数据中，其中有一个数只出现了一次，其他的数都出现了两次，让你来找出一个数 。

有人问如果有2个数出现了一次，其他数都出现了一次，那还能用位运算来找出这两个数吗？

答是必须的，假如这两个出现一次的 数 分别为 A, B，则所有 数 异或后的结果为 A^B，这时我们遇到的问题是无法确定 A，B的值。

由于 A 和 B 是不一样的值，所以 A^B 的结果不为 0，也就是说，这个异或值的二进制中某一位为1。显然，A 和 B 中有且仅有一个数的相同位上也为 1。

这个时候，我们可以把所有 数 分为两类，一类在这个位上为 1，另一类为 0，那么对于这两类，一类会含有 A，另一类会含有 B。于是，我们可以分别计算这两类 数 的异或值，即可得到 A 和 B 的值。