> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/wei-yun-suan/137-zhi-chu-xian-yi-ci-de-shu-zi-ii.md).

# \[137]\[中等] 只出现一次的数字 II

## 题目描述

[137. 只出现一次的数字 II](https://leetcode-cn.com/problems/single-number-ii/) [剑指 Offer 56 - II. 数组中数字出现的次数 II](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/)

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

说明：

你的算法应该具有线性时间复杂度。 你可以**不使用额外空间**来实现吗？

示例 1:

```
输入: [2,2,3,2]
输出: 3
```

示例 2:

```
输入: [0,1,0,1,0,1,99]
输出: 99
```

## 解题思路

参考: [【自动机+位运算】最详细的推导过程，没有之一](https://leetcode-cn.com/problems/single-number-ii/solution/zi-dong-ji-wei-yun-suan-zui-xiang-xi-de-tui-dao-gu/)

首先题目是有空间限制的, **不使用额外的空间**, 否则使用哈希表就能很轻松的解决问题.

要求数字中的数字有一个上限, 这样数字对应的位长就有固定的长度. 将每个数字转换成二级制, 然后对每一位进行考虑.

### 逐位循环

单独的看其中某一位, 如果只出现一次的数字, 在这一位上为0, 则其他所有数字在这一位上为1的数量一定为3的倍数.

因此, 统计每一位为1的数量, 然后模3取余数, 如果余数不为0, 那么单独出现的那个数在这一位上为1, 找到所有为1的位就得到了那个数字的二级制表示.

```python
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        counts = [0] * 32  # 数字位数长度限制, 最后一位表示符号
        for num in nums:
            for i in range(32):
                counts[i] += num & 1
                num >>= 1  # 这样写减少移动的次数

        res = 0
        for i in range(32):
            if counts[i] % 3 != 0:
                res += 1 << i
        return res if counts[31] % 3 == 0 else ~(res ^ 0xffffffff)  # 考虑值为负数的情况
```

### 位计算

[漫画题解](https://leetcode-cn.com/problems/single-number-ii/solution/man-hua-gan-jiu-dui-liao-ao-li-gei-by-ivan1-4/)

上面是循环地对每一位计算1出现的次数, 但我们也可以使用位运算的便利性, 同时对所有位进行计算, 在本题目中, 这种计算相当于**三进制**的加法.

考虑进位, 可以将这种加法表示为如下图所示的**状态机**:

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F6cdfd568a2684de8478066882cf1b6aa27d34a00.jpg?generation=1601089832046619\&alt=media)

有向边上的数字为要加上的数值, 节点中的数字为状态. 因此可以得到如下的状态表:

| state | once | twice |
| ----- | ---- | ----- |
| 0     | 0    | 0     |
| 1     | 1    | 0     |
| 2     | 0    | 1     |

这张表的`state`就是图中的状态. 由于我们要用二级制机制来表示三级制的加法, 为此构造出`once`和`twice`两个辅组的二级制缓存值, 用来表示三级制中的1, 2.

现在我们考虑, 如何以`once`和`twice`代替上图, 表示状态机, 而对于二进制, 就转化成了位运算的问题.

`once`有两种取值, `0`和`1`, 结果为`1`的状态有两种:

* input=1, once=0, twice=0
* input=0, once=1, twice=0

`twice`有两种取值, `0`和`1`, 结果为`1`的状态有两种:

* input=1, once=1, twice=0
* input=0, once=0, twice=1

因此`once`和`twice`的状态转移方程为:

* once = (input ^ once) & (\~twice)
* twice = (input ^ twice) & (once ^ twice)

代码为:

```python
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        once, twice = 0, 0
        for num in nums:
            new_once = (num ^ once) & (~twice)
            twice = (num ^ twice) & (once ^ twice)
            once = new_once
        return once
```