【刷题日记】在 O(n) 内找出只出现 1 次的数字

本文针对 LeetCode 题目中「找出只出现 1 次的数字」3 道系列题，总结题目规律以及位运算的使用方法。

本文题目难度标识：🟩简单，🟨中等，🟥困难。

基础知识

在介绍题目之前铺垫一些涉及到的知识。

异或运算

异或满足交换律和结合律。

$$\begin{aligned} a\oplus 0&=a \\ a\oplus a &= 0 \\ a\oplus b &= b\oplus a \\ (a \oplus b) \oplus c &= a \oplus( b \oplus c) \end{aligned}$$

两个数异或的结果意味着：

• 如果二进制结果中第 i 位为 1，说明这两个数在第 i 位上不相同
• 如果二进制结果中第 i 位为 1，说明这两个数在第 i 位上相同

取出一个整数的二进制表示中的最低位

快速计算补码的非有两种思考方式：

1. 补码的非 -x==~x+1
2. 找出数 x 中最右边的为 1 的位（只要 x 不是 0，总能找到），将这个 1 的左边所有的位取反。

根据第二种思考方式，我们可以得出：取出一个整数的二进制表示中的最低位可以通过 x&-x 得到。

例子

数字 10 的二进制表示： 0b01010
数字 -10 的二进制表示：0b10110
5&-5 的结果： 0b00010

题目与方法

找出 1 个只出现 1 次的数字（其他数字成俩出现）

题目：🟩 136. 只出现一次的数字 - 力扣（LeetCode）

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

方法：将所有数字按位异或，最后得到只出现一次的数字。

这里利用了异或的运算性质：

• 交换律、结合律
• 相同数字异或为 0

复杂度：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

这种方法可以扩展应用于这个问题：数组内某元素 x 出现了奇数次，其他数字出现偶数次，找出这个 x。

找出 1 个只出现 1 次的数字（其他数字成仨出现）

题目：🟨 137. 只出现一次的数字 II - 力扣（LeetCode）

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。 请你找出并返回那个只出现了一次的元素。数组中的元素都在 int（即 32 位整数）范围内。

思路：数组中的元素范围有限，我们可以依次计算答案的每一个二进制位是 0 还是 1。

方法：

• 循环体，复杂度 $O(n)$：遍历 nums 中的每个元素 e
  • 循环体，复杂度 $O(\log C)$：对于每个 e 循环统计所有数字第 i 位出现 1 的次数，得到数组 sum，sum[i] 即表示所有数字第 i 位出现 1 的次数。

假设答案为 x：

• 如果 sum[i] 是 3 的倍数，那么 x 的第 i 位应为 0
• 如果 sum[i] 不是 3 的倍数（余数只能为 1），那么 x 的第 i 位应为 1

复杂度：

• 时间复杂度：$O(n \log C)$，其中 n 时数组的长度，C 是元素的数据范围。本问题中 $C=2^{32}$。
• 空间复杂度：$O(1)$

这个方法引入了一个复杂度 $O(\log C)$，我们可以用有限状态机加速位运算方法（详看后文）进行优化设计。

这种方法可以扩展应用于这个问题：如果数组内元素范围给定，除某 1 个元素 x 仅出现 M 次外，其余每个元素都恰出现 N 次，找出这个 x。（N 为整数且 $N\geq 2$，$M \bmod N\neq 0$）
如果 M 和 N 的奇偶性比较特殊，可以考虑使用异或性质，就如第一个应用那样。

找出 2 个只出现 1 次的数字（其他数字成俩出现）

题目：🟨 260. 只出现一次的数字 III - 力扣（LeetCode）

给你一个整数数组 nums，其中恰好有两个元素 a、b 只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

方法：

• 将 nums 中的所有数字全部异或，得到结果 x。x==a^b，且 x 一定不会是 0
• 取出 x 的二进制表示中最低位的 1：x&-x。假设其为第 l 位。这说明，a 和 b 中，某一个数的第 l 位为 1，另一个数的第 l 位为 0。
• 把 nums 中的所有元素分成两类，其中一类包含所有二进制表示的第 l 位为 0 的数，另一类包含所有二进制表示的第 l 位为 1 的数。我们得到以下结论：
  • 对于任意一个在数组 nums 中出现两次的元素，该元素的两次出现会被包含在同一类中；
  • 对于任意一个在数组 nums 中只出现了一次的元素，即 a 和 b，它们会被包含在不同类中。
• 将每一类的元素全部异或起来，那么其中一类会得到 a，另一类会得到 b

复杂度：

• 时间复杂度：$O(n)$，其中 n 是数组 nums 的长度。
• 空间复杂度：$O(1)$。

这种方法可以扩展应用于这个问题：给定整数数组，有两个元素分别出现奇数次，其余每个元素都恰出现偶数次，找出这个这两个只出现奇数次的元素。
比如：

• 使用位运算解决：🟩 645. 错误的集合 - 力扣（LeetCode）

有限状态机（FSM）加速位运算

线性时间内找出 1 个只出现 1 次的数字（其他数字成仨出现）

题目：🟨 137. 只出现一次的数字 II - 力扣（LeetCode）

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。 请你找出并返回那个只出现了一次的元素。数组中的元素都在 int（即 32 位整数）范围内。

在上文提到的方法中我们是依次处理每一个二进制位的，那么时间复杂度中就引入了 $O(\log C)$ 这一项（对于一个数 e，我们循环统计了 $\log C$ 次）。我们可以直接使用位运算而避免这个循环，也就是下面的数字电路设计优化。

定义两个数组 A 和 B 作为统计结果使用，长度与元素 e 位数相等。A 和 B 中的元素只能是 0 和 1，A[i] 和 B[i] 组成一个统计结果，表明目前遍历的所有 e 中第 i 位的个数（模 3）。比如，遍历 nums 结束后，A[i]=1，B[i]=0，组成二进制数 0b10，表明目前统计的元素中第 i 位为 1 的个数为 2（模 3）。

根据此，进行类似有限状态机 FSM 中描述的设计方法。

方案 1

绘制状态图：

绘制真值表（省略了状态编码等过程，直接一步到位）：

写出输出方程：

\begin{align} a_{i}'&=\overline{a_{i}}b_{i}x_{i}+a_{i}\overline{b_{i}x_{i}} \\ b_{i}'&=\overline{a_{i}b_{i}}x_{i}+\overline{a_{i}}b_{i}\overline{x_{i}} = \overline{a_{i}}(b_{i}\oplus x_{i}) \\ \end{align}

将电路逻辑转换为等价的位运算：

a = (~a & b & x) | (a & ~b & ~x)
b = ~a & (b^x)

在这题中碰巧的是，B 数组组成的二进制数就是所求（因为最终的统计结果中，余数只能是 0 或 1）。

• 时间复杂度：$O(n)$，其中 n 是数组 nums 的长度。
• 空间复杂度：$O(1)$。

方案 2

在上一个方案中计算 b 简单，计算 a 麻烦。因此可以将「同时计算」改为「分别计算」，即先计算出 b，再拿新的 b 值计算 a。

也就是说，我们拿新的 b’ 改造一下真值表，看看能不能把电路优化。

进一步优化：

重新写出 a 的输出方程：

$$a_{i}'=\overline{a_{i}b_{i}'}x_{i}+a_{i}\overline{b_{i}'x_{i}} = \overline{b_{i}'}(a_{i}\oplus x_{i})$$

将电路逻辑转换为等价的位运算：

b = ~a & (b^x) // b先计算
a = ~b & (a^x)

• 时间复杂度：$O(n)$，其中 n 是数组 nums 的长度。
• 空间复杂度：$O(1)$。

本文参考

• 《深入理解计算机系统》第 3 版，「数制与编码」章节
• LeetCode 原题——只出现一次的数字 I、II、III