我们再来看只出现一次的数字 II这道题，除了前面讲的解决方式以外，我们还可以使用有限状态机。如果想要了解有限状态机，最好能有数字电路设计的基础。我们这样思考一下，假设有一种运算符 *，它具有以下功能。
1 * 1 * 1 = 0
1 * 0 = 1
0 * 1 = 1
1 * 1 = x
这个 x 是多少暂且不管，我们只知道这个运算符 *（我们自己发明的）具有交换律，并且每 3 个相同的数字通过这个运算符运算之后结果为 0 ，那么这道题就很容易解了，只需要把数组中的所有数字都通过这个运算符运算一遍即可，但问题的关键是怎么来设计这个运算符呢？
我们看到上面有 3 种状态分别是 0,1,x ，如果是两种状态可以使用 0 和 1 表示，只需要 1 位数，如果是 3 种状态至少需要 2 位数，注意这里是至少，你也可以使用 3 位， 4 位，5 位 …… 都是可以的，关键是要找好他们之间的转化关系。这里我们就以 2 位来分析下，要注意 0 和任何数字运算的结果都不变。按照题意的要求，如果某个数出现 4 次，就让他的结果变成出现 1 次，也就是说周期是 3 ，每个数都会有下面几种状态。
出现 1 次
出现 2 次
出现 3 次
看到这里其实大家已经想到了，这不就是传说中的 3 进制吗？在二进制中一个位置要么是 1 要么是 0 ，只能表示两种状态，如果要表示 3 种状态我们可以使用两位数字来表示。
00表示出现 1 次
01表示出现 2 次
10表示出现 3 次
如果输入的是0（状态始终不变）
| 0 出现的次数 | XY（输入之前的状态） | 输入数字 | XY（输入之后的状态） |
|---|---|---|---|
| 1 | 00 | 0 | 00 |
| 2 | 01 | 0 | 01 |
| 3 | 10 | 0 | 10 |
如果输入的是1（始终跳到下一个状态）。
| 1 出现的次数 | XY（输入之前的状态） | 输入数字 | XY（输入之后的状态） |
|---|---|---|---|
| 1 | 00 | 1 | 01 |
| 2 | 01 | 1 | 10 |
| 3 | 10 | 1 | 00 |
输入和输出的关系知道了，下面我们来找一下他们的推导公式，先看一下输入之后状态 x 为 1 的有哪些，一个是 0 出现次数为 3 的那行，一个是 1 出现次数为 2 的那行，所以我们可以得出。
X = (X & ~Y & ~num) | (~X & Y & num)
这里num是输入的数字
如果看不懂的可以先看下卡诺图化简法，这是数字电路设计中的知识（如果大学没学过的，这里可以先跳过）。其实很简单，如果是 1 就用原来的数字表示，如果是 0 就在前面添加非运算符 ~ ，关于数电的知识这里就不在过多展开。同理我们还可以推导出 Y 。
Y = (~X & Y & ~num) | (~X & ~Y & num)
通过上面表格我们可以看到如果 0 出现一次的话结果是 00 ，如果 1 出现一次的话结果是 01 ，所以无论输入的是 0 还是 1 ，如果只出现 1 次的话，结果就会保存在 Y 中，最后我们只需要返回 Y 的值即可。当然这里 X 和 Y 还是可以化简的，如果对卡诺图化简法不是很了解的话，我们不用化简，直接运行也是没问题的。
public int singleElement(int[] nums) {
int x = 0;
int y = 0;
for (int num : nums) {
// 为了防止变量x被覆盖，这里先把计算的结果保存起来，最后在赋值给x。
int tmp = x & ~y & ~num | ~x & y & num;
y = ~x & y & ~num | ~x & ~y & num;
x = tmp;
}
return y;
}
上面我们说过，无论是使用 2 位数， 3 位数， 4 位数 …… 都是可以的，只要能存储下 3 种状态即可，下面我们就用一个 3 位数来计算下， 3 位数可以表示 8 种状态，可以随便选。
001 表示 1 次
010 表示 2 次
100 表示 3 次
如果输入的是0（状态始终不变）。
| 0 出现的次数 | XYZ（输入之前的状态） | 输入数字 | XYZ（输入之后的状态） |
|---|---|---|---|
| 1 | 001 | 0 | 001 |
| 2 | 010 | 0 | 010 |
| 3 | 100 | 0 | 100 |
如果输入的是1（始终跳到下一个状态）。
| 1 出现的次数 | XYZ（输入之前的状态） | 输入数字 | XYZ（输入之后的状态） |
|---|---|---|---|
| 1 | 001 | 1 | 010 |
| 2 | 010 | 1 | 100 |
| 3 | 100 | 1 | 001 |
根据上面的状态我们可以推出转换关系如下。
X = X & ~Y & ~Z & ~num | ~X & Y & ~Z & num
Y = ~X & Y & ~Z & ~num | ~X & ~Y & Z & num
Z = ~X & ~Y & Z & ~num | X & ~Y & ~Z & num
上面我们并没有化简，通过上面的表看到无论是 0 还是 1 ，如果只出现 1 次他们都会保存在 Y 中，所以最后只需要返回 Y 即可。
public int singleElement(int[] nums) {
int x = 0;
int y = 0;
// 因为我们定义的001表示的是1次，所以初始化的时候让z的二进制位全部
// 变为1，-1的二进制表示为11111111 11111111 11111111 11111111
int z = -1;
for (int num : nums) {
int tmpX = x & ~y & ~z & ~num | ~x & y & ~z & num;
int tmpY = ~x & y & ~z & ~num | ~x & ~y & z & num;
z = ~x & ~y & z & ~num | x & ~y & ~z & num;
x = tmpX;
y = tmpY;
}
return y;
}
在 int 范围内能表示 3 种状态的可以挑选上亿个都不止，那么这样写下去答案就比较多了。
