题型
我们的问题是：“给出一个整型数组，每个元素都出现 k （k>1）次，只有一个元素出现 p 次（p >= 1，p % k != 0）。找到这个单独的元素。”
详细思路
如其他人指出的，为了执行位运算操作，我们应该考虑整数在计算机中是如何表示的——通过位。首先我们考虑一位。假设我们有一个一位数字（只能为0或者1）组成的数组，我们可以计算数组中1出现的次数，每次计算的1的次数达到一个特定的值，也就是k时，计算归0并且重新开始（以防你混淆，这里的k就是题目中的k）。要记录我们计算了多少1，就需要一个计数器。假设计数器有m位，二进制表示为：xm, ..., x1（从最高位到最低位）。我们至少可以推断出计数器的下面四个特性：
1、计数器有一个初始值， 一般就是0；
2、对于数组的每次输入，如果我们遇到0，计数器保持不变；
3、对于数组的每次输入，如果我们遇到1，计数器应该增加1；
4、要覆盖k次，我们需要 2^m >= k，也就是 m >= logk。
关键部分是：在我们浏览数组时如何改变计数器中的每一位（x1到xm）。注意我们可以用位运算操作。要保证第二个特性，回想一下那个位运算操作不会在另一个运算元是0时改变本身？对，就是 x = x | 0 和 x = x ^ 0。
好，我们现在有表达式 x = x | i 或者 x = x ^ i，i 就是数组中的元素。哪个更好？我们现在还不知道。所以我们先做一下实际的计算：
一开始，计数器的所有位都初始化位0，比如，xm = 0, ..., x1 = 0。因为我们要选择位操作来保证在遇到0时计数器的所有位保持不变，直到我们在数组中遇到了1。遇到第一个1之后，我们得到：xm = 0, ..., x1 = 1。然后我们继续下去直到遇到第二个1，这时我们就有：xm = 0, ..., x2 = 1, x1 = 0。注意x1从1变为0了。对于 x1 = x1 | i，在第二次计算时，x1还会是1。所以很明显我们应该用 x1 = x1 ^ i。那 x2, ..., xm 呢？关键是要找到 x2, ..., xm 什么时候会变。拿 x2 做例子。如果我们遇到 1 并且需要改变 x2 的值，那我们做这个操作时 x1 一定是什么？答案是：x1 必须是1，否则我们不应该改变 x2 ，而是应该将 x1 从 0 改为 1。所以只有当 x1 和 i 都为 1 时才应该改变 x2，写成公式就是 x2 = x2 ^ (x1 & i)。类似的 xm 也只会在 xm-1, ..., x1 和 i 都为 1 时改变：xm = xm ^ (xm-1 & ... & x1 & i)。这样我们就找到了需要的位操作了。
然而，你可能会注意到上面的位操作会从 0 一直计算到 2^m - 1，而不是 k。如果 k < 2^m - 1，我们需要在计算到 k 时进行一些切断操作来将计数器归零。为此，我们给 xm, ..., x1 加上与操作，以及一个变量 mask。比如，xm = xm & mask, ..., x1 = x1 & msak。如果我们可以保证 mask 只有在计算到 k 时变为 0，而其他的时候都为 1，就达到要求了。如何做到呢？想想区分 k 次与其他次数的是什么？对，就是 1 的个数！对于每一次，我们有一个唯一的值对于计数器的每一位，可以被认为是它的状态。如果我们将 k 写成二进制形式：km, ..., k1。我们可以如下构造 mask：
mask = ~(y1 & y2 & ... & ym)，其中如果 kj = 1 则 yj = xj，如果 kj = 0 则 yj = ~xj（j 从 1 到 m）。
举一些例子：
k = 3：k1 = 1, k2 = 1, mask = ~(x1 & x2)；
k = 5：k1 = 1, k2 = 0, k3 = 1, mask = ~(x1 & ~x2 & x3)；
所以，我们的算法就会像下面这样：
for (int i : array) {
xm ^= (xm-1 & ... & x1 & i);
xm-1 ^= (xm-2 & ... & x1 & i);
.....
x1 ^= i;
mask = ~(y1 & y2 & ... & ym) where yj = xj if kj = 1 and yj = ~xj if kj = 0 (j = 1 to m).
xm &= mask;
......
x1 &= mask;
}
现在，是时候将我们的结果从 1 位数字升级到 32 位数字了。一个直接的方法是为数字中的每一位一共创建32个计数器。你可能在别的代码中看到了这个做法。但是如果我们采用位操作，我们就可以“集中”管理所有32个计数器。这里的“集中”是指使用 m 个32位整数而不是32个 m位计数器，m 是满足 m >= logk 的最小整数。原因是位操作只会影响每一位本身，所以每一位的操作都是独立于其他位的（很明显是吧）。这样我们就可以将32个计数器组合为一个32位整数。因为每个计数器都有m位，我们最后就会有m个32位整数。因此，上面的代码中，我们只需要将 x1 到 xm 从一位数字看做32位整数就可以了。很简单是吧。
最后一件事是我们应该返回什么值，或者说 x1 到 xm 中哪个是唯一的元素。要得到准确的答案，我们需要理解 m 个32位整数 x1 到 xm 代表什么。拿 x1 为例。 x1 有32位，我们将它们标记为 r（r = 1 到 32）。在我们扫描完输入的数组后，x1 的 r-th 的值由数组中所有元素的 r-th 位决定（更明确的说，假设所有元素的 r-th 位的1的总数是q，q' = q % k 并且其二进制形式为：q'm, ..., q'1，根据定义 x1 的 r-th 位会等于 q'1）。现在你可以问你自己这个问题：如果 x1 的 r-th 位是 1，这代表了什么？
答案要看什么会导致这个1。是出现了 k 次的元素导致的吗？不是的，为什么？因为一个导致此的元素，必须同时满足两个条件：这个元素的 r-th 位是1，并且这个1出现的次数不是k的倍数。第一个条件不重要。第二个条件是因为每当1出现k次后计数器都会归零，这也就意味着x1的每一位会被设为0。对于出现了k次的元素，不可能同时满足这两个条件，所以不会是它导致的。只有唯一的那个出现了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 位）。这里我声明 x1 等于唯一元素的条件是 p'1 = 1。快速证明：如果 x1 的 r-th 位是1，我们可以说 唯一元素的 r-th 位也是1。可以证明如果 x1 的 r-th 位是0，那么唯一元素的 r-th 位也是0。只要假设唯一元素的 r-th 位是1，看看会发生什么。在扫描的最后，这个1会被记录 p' 次。如果我们将 p' 写为二进制形式：p'm, ..., p'1，根据定义 x1 的 r-th 位会等于 p'1，也就是1。这与 x1 的 r-th 位是0相反。所以对于x1的所有位都是这样的，我们可以推断如果p'1等于1，x1会等于唯一元素。类似的我们可以推断如果p'j = 1（j = 1 到 m），xj 会等于唯一元素。现在我们要返回什么就很清晰了。只要令 p' = p % k，转成二进制形式，只要 p'j = 1 就返回 xj。
总的来说，这个算法的时间复杂度是O(n * logk)，空间复杂度是O(logk)。
举例：
1、k = 2, p = 1
这就是说数组中其余数字都出现两次，只有一个数字出现了一次，找到这个数字：
public int singleNumber(int[] A) {
int x1 = 0;
for (int i : A) {
x1 ^= i;
}
return x1;
}
2、k = 3, p = 1
数组中其余数字都出现三次，只有一个数字出现一次，找到这个数字：
public int singleNumber(int[] A) {
int x1 = 0;
int x2 = 0;
int mask = 0;
for (int i : A) {
x2 ^= x1 & i;
x1 ^= i;
mask = ~(x1 & x2);
x2 &= mask;
x1 &= mask;
}
return x1; // p = 1, 二进制形式为 p = '01', 所以 p1 = 1, 我们应该返回 x1;
// 如果 p = 2, 二进制形式为 p = '10', 所以 p2 = 1, 我们就要返回 x2.
}
3、k = 5, p = 3
数组中其余数字都出现五次，只有一个数字出现三次，找到这个数字：
public int singleNumber(int[] A) {
int x1 = 0;
int x2 = 0;
int x3 = 0;
int mask = 0;
for (int i : A) {
x3 ^= x2 & x1 & i;
x2 ^= x1 & i;
x1 ^= i;
mask = ~(x1 & ~x2 & x3);
x3 &= mask;
x2 &= mask;
x1 &= mask;
}
return x1; // p = 3, 二进制形式为 p = '011', 所以 p1 = p2 = 1,
// 我们应该返回 x1 或者 x2;
// 但如果 p = 4, 二进制形式为 p = '100', 只有 p3 = 1,
// 我们就只能返回 x3.
}
网友评论