题目要求的时间复杂度均为 $O(n)$
给出一个数组，里面有一个数出现了一次，其余出现了两次，找出这个数。
异或运算记为 $a \otimes b$ ，作用是对于 $a$ 和 $b$ 的每一位做运算，相同则此位为0，不同为1，同时异或运算支持交换律，即 $a \otimes b = b \otimes a$ ，同时对于任意的 $a$ ， 有 $ a \otimes a = 0$ 。
对于这个问题，只需要将所有数异或起来就是答案。
给出一个数组，里面有两个数出现了一次，其余出现了两次，找出这两个数。
设 $x = a \otimes b$ ，那么 $x \ne 0$ ，所以 $\exists\ k \ge 0\ \ \ x\ and \ 2^k ==2^k $ ，那么 $2^k$ 与 $a$ 和 $b$ 做 $and$ 运算，得到的结果一定是一个为 $0$ ，一个不为 $0$ 。所以拿 $2^k$ 去与所有的数做 $and$ 运算，为 $0$ 的放在第一个数组，不为 $0$ 的放在第二个数组，$a$ 和 $b$ 一定在不同的数组里面，接下来只要把两个数组所有的数分别异或起来，得到的就是 $a$ 和 $b$ 。
给出一个数组，里面有三个数出现了一次，其余出现了两次，找出这三个数。
$x = a \otimes b\otimes c$ 。
如果 $x$ 为 $0$ ，那么去找一个位 $m$ ，使得所有的数与 $2^m$ 做 $and$ 操作后分成两个数组，如果两个数组异或起来均不为 $0$ ，那么奇数个元素的数组异或起来的值就是所求的第一个数，另外一个数组可以转化为第二个问题。
如果 $x$ 不为 $0$ ，记 $f(x) =x\ and\ -x$ ，即求得 $x$ 最小的那一位 $1$ 。记 $A=f(x\otimes a)\ \ B=f(x\otimes b)\ \ C=f(x\otimes c)$ ，那么 $A\otimes B\otimes C$ 一定不为 $0$ ， 因为对于任意不为 $0$ 的 $x$ 和 $y$ ， $f(x) \otimes f(y)$ 肯定为 $0$ 或者 $2$ 个 $1$ 。记 $f(A \otimes B\otimes C)==2^m$ ，又因为三个数互相异或，产生的数只可能是 $3$ 个 $0$ 或者 $2$ 个 $1$ 和 $1$ 个 $0$ ，而 $A \otimes B\otimes C$ 在第 $m$ 位是 $1$ ，所以 $a\ \ b\ \ c$ 在 $m$ 位一定是 $2$ 个 $1$ 和 $1$ 个 $0$ ，或者 $2$ 个 $0$ 和 $1$ 个 $1$ ，那么只要根据第 $m$ 位将数组划分为两组，奇数组异或起来就是所求的第一个数，偶数组可以转化为第二个问题。