这里我们结合位运算和数字电路，教会大家如何写出有限状态机的状态转移方程。我们这里先以异或消除相同数字的例题为例，引出我们的通过状态机消除三个相同的数字的例题。
剑指 Offer 56 - I. 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]限制：
2 <= nums.length <= 10000
思路: 分组异或
我们知道，如果除了一个数字以外，其他数字都出现了两次，那么如何找到出现一次的数字？答案很简单：全员进行异或操作即可。
那么这一方法如何扩展到找出两个出现一次的数字呢？
如果我们可以把所有数字分成两组，使得：
- 两个只出现一次的数字在不同的组中；
- 相同的数字会被分到相同的组中。
那么对两个组分别进行异或操作，即可得到答案的两个数字。这是解决这个问题的关键。
那么如何实现这样的分组呢？
如果我们把 任意一个数\(x\) 写成二进制的形式\(x_k x_{k - 1} \cdots x_2 x_1 x_0\)，其中 \(x_i \in \{ 0, 1 \}\)。如果要满足条件2，那么就得保证每一位\(x_i\)都是相等的。
记这两个只出现了一次的数字为 \(a\) 和 \(b\)，那么所有数字异或的结果就等于 \(a\)和 \(b\)异或的结果，我们记为 \(xor\)。
如果要满足条件1，那么只需要找到一位\(k\)，使得\(a_k \neq b_k\)即可。那么这个时候必然有\(xor_k = 1\)。
在实际操作的过程中，我们拿到序列的异或和 \(x\) 之后，对于这个「位」是可以任取的，只要它满足 \(x_i = 1\)。但是为了方便，这里的代码选取的是「不为 \(0\) 的最低位」，当然你也可以选择其他不为 \(0\) 的位置。
算法
- 先对所有数字进行一次异或，得到两个出现一次的数字的异或值。
- 在异或结果中找到任意为
1的位。 - 根据这一位对所有的数字进行分组。
- 在每个组内进行异或操作，得到两个数字。
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int ret = 0;
for (int n : nums)
ret ^= n;
int div = 1;
while ((div & ret) == 0)
div <<= 1;
int a = 0, b = 0;
for (int n : nums)
if (div & n)
a ^= n;
else
b ^= n;
return vector<int>{a, b};
}
};复杂度分析
- 时间复杂度：\(O(n)\)，我们只需要遍历数组两次。
- 空间复杂度：\(O(1)\)，只需要常数的空间存放若干变量。
剑指 Offer 56 - II. 数组中数字出现的次数 II
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3]
输出：4示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1限制：
1 <= nums.length <= 100001 <= nums[i] < 2^31
解题思路：
我们知道，使用异或消除出现两次的数字，本质上是因为各二进制位出现的次数都是2的倍数，采用异或运算后都为0。
同样的，对于出现三次的数字，如下图所示，考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 3 的倍数。
因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。
由于各二进制位的 位运算规则相同 ，因此只需考虑一位即可。我们可以使用有限状态自动机
如下图所示，对于所有数字中的某二进制位 1 的个数，存在 3 种状态，即对 3 余数为 0, 1, 2 。
- 若输入二进制位 1 ，则状态按照以下顺序转换；0→1→2→0→⋯
- 若输入二进制位 0 ，则状态不变。
如下图所示，由于二进制只能表示 0, 1，因此需要使用两个二进制位来表示 3 个状态。设此两位分别为 two, one ，则状态转换变为：
\(00→01→10→00→⋯\)
接下来，需要通过 状态转换表 导出 状态转换的计算公式 。我们写出状态转化表如下：
这是什么？这不就是数字电子技术中的组合逻辑电子电路设计吗！根据真值表写出逻辑函数式。
\(one = n{'} \cdot two{'} \cdot one + n \cdot two{'} \cdot one{'} = two{'} \cdot (n{'} \cdot one+n \cdot one{'} ) = two{'}(n \oplus one) \\\)
计算two时候需要注意，由于是先计算 one ，因此应在新 one 的基础上计算 two 。
如下图所示，修改为新 one 后，得到了新的状态图。观察发现，可以使用同样的方法计算 two ，即：
根据第二个状态转移图，同样画出真值表，可以得出逻辑函数式
\(two = n{'} \cdot two \cdot one(new){'} + n \cdot two{'} \cdot one(new){'} = one(new){'}(n \oplus two)\)
以上是对数字的二进制中 “一位” 的分析，而 int 类型的其他 31 位具有相同的运算规则，因此可将以上公式直接套用在 32 位数上。
遍历完所有数字后，各二进制位都处于状态 00 和状态 01 （取决于 “只出现一次的数字” 的各二进制位是 1 还是 0 ），而此两状态是由 one 来记录的（此两状态下 two 恒为 0 ），因此返回 one 即可。
代码
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ones = 0,twos = 0;
for(auto& x: nums){
ones = ~twos&(x^ones);
twos = ~ones&(x^twos);
}
return ones;
}
};复杂度分析：
- 时间复杂度 \(O(N)\)： 其中 NN 位数组 \(nums\) 的长度；遍历数组占用 \(O(N)\)，每轮中的常数个位运算操作占用 \(O(32\times 3\times 2)=O(1)\)。
- 空间复杂度\(O(1)\)： 变量 \(ones\) , \(twos\)使用常数大小的额外空间。