题型：
给出一个整型数组，每个元素都出现 $k$ （$k>1$）次，只有一个元素出现 $p$ 次（$p \geq 1$，$p \% k != 0$）。找到这个单独的元素。
详细思路：
我们能想到的最直接的方法就是用 $map$ 标记每个元素出现了多少次，然后找出次数为 $p$ 次的元素，但是这样的空间复杂度就十分的高，这里我们有另外的做法：位运算
首先我们考虑一位。假设我们有一个一位数字（只能为 $0$ 或 $1$ ）组成的数组，我们可以计算数组中 $1$ 出现的次数，每次计算的 $1$ 的次数达到一个特定的值，也就是 $k$ 时，计算归 $0$ 并且重新开始（以防你混淆，这里的 $k$ 就是题目中的 $k$ ）。要记录我们计算了多少 $1$ ，就需要一个计数器。假设计数器有 $m$ 位，二进制表示为：$x_m,…,x_1$（从最高位到最低位）。我们至少可以推断出计数器的下面四个特性：
- 计数器有一个初始值，一般就是 $0$ ；
- 对于数组的每次输入，如果我们遇到 $0$，计数器保持不变；
- 对于数组的每次输入，如果我们遇到 $1$，计数器应该增加 $1$;
- 要覆盖$k$次，我们需要$2^m \geq k$，也就是$m \geq log(k)$。
关键部分是：在我们浏览数组时，如何改变计数器中的每一位（$x_1$到$x_m$）。注意我们可以用位运算操作。那要保持第二、三个特性，或操作和异或操作都可以满足，即$x = x | 0$ 和$x = x \bigwedge 0$。
由于这里还不能确定$x = x | 0$ 和$x = x \bigwedge 0$两个表达式哪个更好，这里我们就来做一下实际的运算：
一开始，计数器的所有位全都初始化为 $0$，比如$x_m = 0, …, x_1 = 0$。因为我们要选择位运算来保证第二、三个特性，直到我们在数组中遇到了 $1$。遇到第一个$1$之后，我们得到：$x_m = 0, …, x_1 = 1$。然后我们继续下去知道遇到第二个$1$，这时我们就有：$x_m =0, …, x_2 = 1, x_1 = 0$。注意 $x_1$ 从 $1$ 变为 $0$ 了，对于$x_1 = x_1 | i$，在第二次计算时，$x_1$还会是 $1$，所以很明显我们应该用$x = x \bigwedge i$。
那$x_2, …, x_m$呢？关键是要找到$x_2, …, x_m$什么时候会变。拿$x_2$为例子，如果我们遇到$1$并且需要改变 $x_2$ 的值，那我们做这个操作时 $x_1$ 一定要是 $1$，否则我们不应该改变 $x_2$，而应该是将 $x_1$ 从 $0$ 改为 $1$。所以只有当 $x_1$ 和 $i$ 都为 $1$ 时才应该改变 $x_2$，写成公式就是$x_2 = x_2 \bigwedge (x_1 \& i)$ 。类似的 $x_m$ 也只会在 $x_{m - 1}, …, x_1$ 和 $i$ 都为 $1$ 时改变：$x_m = x_{m - 1} \bigwedge (x_{m - 1} \& … \& x_1 \& i)$。这样我们就找到了需要的位运算操作了。
然而，你可能会注意到上面的位操作会从$0$一直计算到$2^m - 1$，而不是$k$。如果$k < 2^m - 1$，我们就需要在计算到$k$时进行一些操作来让计数器归零。
为此，我们给$x_m, …, x_1$加上与操作，以及一个变量 $mask$。比如$x_m = x_m \& mask, …, x_1 = x_1 \& mask$。如果我们可以保证 $mask$ 只有在计算到$k$时变为$0$，而其他时候都为 $1$，就达到要求了。
那么区分$k$次和其他次数的就是$1$的个数，对于每一次，我们有一个唯一的一个值对于计数器的每一位，可以被认为是它的状态。如果我们将$k$写成二进制形式：$k_m, …, k_1$。我们可以如下构造$mask$：
$mask = \thicksim(y_1 \& y_2 \& … \& y_m)$,其中如果$k_j = 1$则$y_j = x_j$，如果$k_j = 0$则$y_j = \thicksim x_j$（$j$从$1$到$m$）。
最后一件事情就是我们应该返回什么值，或者说从 $x_1$ 到 $x_m$ 中哪个是唯一的元素。
要得到准确的答案，我们需要理解 $m$ 个 $32$ 位的整数 $x_1$ 到 $x_m$ 代表什么。拿 $x_1$ 为例，$x_1$ 有 $32$ 位，我们将这些位数标记为 $r$（$r = 1, …, 32$）。在我们扫描完输入的数组后，$x_1$的第 $r$ 位的值由数组中所有元素的第 $r$ 位决定（更明确的说，假设所有元素的第 $r$ 位的 $1$ 的总数是 $q$ ，$q’ = q \% k $ 并且其二进制形式为：$q’_m, …, q’_1$，根据定义$x_1$的第 $r$ 位会等于 $q’_1$）。现在就是如果$x_1$的第 $r$ 位是 $1$，这代表什么？
我们需要知道的就是为什么会导致这个 $1$。会导致 $1$，必须同时满足两个条件：
- 这个元素的第 $r$ 位是 $1$，并且这个 $1$ 出现的次数不是 $k$ 的倍数。
- 每当 $1$ 出现 $k$ 次后计数器都会归零，也就意味着 $x_1$的每一位会被设为 $0$。
这两个条件也就排除了出现 $k$ 次的元素的原因，那么会导致$x_1$的第 $r$ 位是 $1$，就只有出现了 $p$（$p \% k != 0$）次的元素导致。如果 $p > k$ ，那么前面的 $k * [p / k]$ （$[p / k]$表示 $[p / k]$ 的证书结果）次都不会导致。所以我们可以总是令 $p’ = p \% k$ 并说唯一元素出现了有效的 $p’$次。
将 $p’$ 写为二进制形式：$p’_m, …, p’_1$（注意 $p’ < k$，所以它可以写成 $m$ 位）。这里我声明 $x_1$ 等于唯一元素的条件是 $p’_1 = 1$。
快速证明：
如果 $x_1$ 的第 $r$ 位为 $1$，我们可以说唯一元素的第 $r$ 位也是 $1$。
如果 $x_1$ 的第 $r$ 位为 $0$，那么唯一元素的第 $r$ 位也为 $0$。
假设唯一元素的第 $r$ 位为 $1$，那么在扫描的最后，这个 $1$ 会被记录 $p’$ 次，如果我们将 $p’$ 写为二进制形式：$p’_m, …, p’_1$，根据定义 $x_1$ 的第 $r$ 位会等于 $p’_1$，也就是 $1$。这时与 $x_1$ 的第 $r$ 位为 $0$ 相反。所以对于所有的 $x_1$ 的所有位都是这样的，我们可以推断如果 $p’_1 = 1$，$x_1$ 会等于唯一元素。类似的我们可以推断如果 $p’_j = 1$（$j = 1, …, m$），$x_j$ 会等于唯一元素。
现在我们要返回什么就很清晰了，只要令 $p’ = p \% k$，转成二进制形式，只要 $p’_j = 1$ 就返回 $x_j$。
总的来说，这个算法的时间复杂度为 $O(n*log(k))$，空间复杂度为 $O(log(k))$。
举例：
1、$k = 2, p = 1$
这就是说数组中其余数字都出现两次，只有一个数字出现了一次，找到这个数字：
1 | public int singleNumber(int[] A) { |
2、$k = 3, p = 1$
数组中其余数字都出现三次，只有一个数字出现一次，找到这个数字：
1 | public int singleNumber(int[] A) { |
3、$k = 5, p = 3$
数组中其余数字都出现五次，只有一个数字出现三次，找到这个数字：
1 | public int singleNumber(int[] A) { |