那些年我们学过的卡诺图

先来看一道面试题：

给出 3n + 1 个数字，除其中一个数字之外其他每个数字均出现三次，要求找出这个数字。  
例如：给出 [1,1,2,3,3,3,2,2,4,1]，返回 4。要求做到一次遍历，O(1) 的空间复杂度。

解法一：

将每个数字都用二进制表示，那么可以把每一位的结果进行相加（十进制加），然后再对 3 取余，那么每一位的结果只能是 0 或者 1，而这个最终的结果就是要找出的那个数字。

python code

def singleNumber(self, nums):
    counts = [0] * 32
    result = 0
    for i in range(32):
        for num in nums:
            if (num >> i) & 1:
                counts[i] += 1
        result |= (counts[i] % 3) << i
    return result

这个解法时间复杂度是 O(n)，但需要 32 次遍历，严格来说并不符合题目要求。

注意实现语言：在 python 中，int 类型的位数是随操作系统而变的。在 64 位系统上运行以上的代码在碰到负数时（涉及到补码）就会有问题。而 java, c, c++，默认的 int 都是 32 位，所以在上述代码中 hardcode 32 不会有问题。

解法二：

解法一之所以要用十进制加（并用一个额外数组来存储）是因为一个二进制 bit 无法存储四种状态：0 -> 1 -> 2 -> 3 。（如果将对 3 取余也算在内，那么只有三个状态 0 -> 1 -> 2 -> 0）

那么，为什么不用两个 bit 来表示呢？答案是肯定的：00 -> 01 -> 10 -> 00。

而且这两个 bit 表示的状态变化是可以枚举的：假设用 A, B 来表示当前的状态，C 表示输入，则 f(A) 和 f(B) 可以表示变化后的状态。

还记得这个表的术语吗？出计算机必修课《数理逻辑》：真值表。

现在的问题就变成能不能从上面的真值表推导出 f(A) 和 f(B) 的公式？一种暴力的方法就是肉眼推导，毕竟也只有 6 种状态变化。譬如可以看出 f(B) 有 5 种情况下都等于 B xor C；只有第 6 种情况是个例外 。再仔细观察，可以发现当 A 等于 1 时，f(B) 都等于 0。所以结合可以得到：f(B) = B xor C & ~A （~A 为对 A 取反）。

继续观察 f(A)前，要注意一下 f(A) 的输入变量：在写程序时，如果先计算出了 f(B)，那么 f(A) 的输入就应该是 A，f(B)，C，而不是 A，B，C —— 因为 f(B) 已经是 B 的下一个状态了。

继续观察真值表，不难得出 f(A) = A xor C & ~f(B)。

至此，我们就可以用 AB 来表示某个 bit 上的状态变化，同理，对于题目中的数字上的所有 bit 都可以适用（因为没有进位）：

那么现在就可以写程序来求解了：遍历所有数字，每个位上的两进制表示与 AB 进行刚才推导出的函数计算，最终的 B 就是所求的数字。（如果题目更改为 3n + 2 个数字，只有一个数字出现 2 次，则返回 A ）

python code

def singleNumber(nums):
    a, b = 0, 0
    for num in nums:
        b = (b ^ num) & ~a
        a = (a ^ num) & ~b
    return b

卡诺图

刚才我们用的「肉眼」 观察法显然是非正规军。。经过理论验证的方法是卡诺图法（Karnaugh map）。

由 f(B) 的卡诺图：

tip： 注意 AB 和 C 的值变化都只能变动 1 位，如 AB 就不能从 00 变至 11。听起来熟悉吧，这东西叫做格雷码（Grey Code）。

可得出：

f(B) = ~A & B & ~C | ~A & ~B & C
     = ~A & ( B & ~C | ~B & C) 
     = ~A & (B xor C)

由 f(A) 的卡诺图：

可得出：

f(A) = ~A & C & ~f(B) | A & ~C & ~f(B) 
     = ~f(B) & (~A & C | A & ~C)
     = ~f(B) & (A xor C)

举一反三

如果题目改为：

给出 5n + 1 个数字，除其中一个数字之外其他每个数字均出现 五 次，要求找出这个数字。

尝试着给出解吧 :-)