the leetcode link

剑指 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 <= 10000
1 <= nums[i] < 2^31

解题思路

本题解主要是根据k神题解的有限状态自动机思路，补充了一些数据结构的可视化，方便大家理解。

一个结论

如果所有数字都出现3次，把所有数字的每一个二进制位分别求和，各位置的结果均为 3 的倍数。
对于本题，我们分别统计所有数字的每二进制位中 1 的出现次数，并把各位置的结果分别对 3 求余，结果得到只出现一次的数字。
比如： [3,4,3,3]
| 0 | 0 | 0 | 1 | 1 |
|—-|—-|—-|—-|—-|
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 1 |
出现次数：
| 0 | 0 | 1 | 3 | 3 |
|—-|—-|—-|—-|—-|
模3：
| 0 | 0 | 1 | 0 | 0 |
|—-|—-|—-|—-|—-|
得到结果：4

方法：有限状态自动机

对于所有数字中的某二进制位 1 的个数mod 3，会得到3个结果，即存在3种状态：0,1,2。

1bit只有0和1，无法表示3种状态。

于是，我们把每二进制位的位置，用2bit表示：00，01，10
比如：
各位的出现次数及其对应的mod3状态：
| 0 | 0 | 1 | 2 | 3 |
|—-|—-|—-|—-|—-|
| 00 | 00 | 01 | 10 | 00 |

• 对于每一个二进制位置，累加过程mod3的状态转移是循环的：
  出现0次：00 -》 出现1次：01 -》 出现2次：10 -》出现3次：00 -》出现4次：01 …
• 对于不同两个二进制位置，状态同步转移，比如一个位出现1次，另一个位出现4次，此时次数mod3状态是一致的，当新累加一个数，两者状态都要一次转移，可能入0转移到自己，可能入1就到下个状态。

Q：这样2bit的结构具体如何在代码中表达？

定义两个变量表示当前mod3状态：ones，twos
ones表示所有2bit二进制位的所有第一位；
twos表示所有2bit二进制位的所有第二位；
比如：
出现次数mod3状态：
| 00 | 00 | 10 | 01 | 01 |
|—-|—-|—-|—-|—-|
ones是：
| 0 | 0 | 0 | 1 | 1 |
|—-|—-|—-|—-|—-|
twos是：
| 0 | 0 | 1 | 0 | 0 |
|—-|—-|—-|—-|—-|

状态转移方程推导

对于某一个二进制位：
定义第一位one，第二位two，新累加二进制位数：n

if two == 0 && one == 0:
  if n == 1:
    one = ~one  # one = 1
    two = two   # two = 0

if two == 0 && one == 1:
  if n == 1:
    one = ~one  # one = 0
    two = ~two  # two = 1

if two == 1 && one == 0:
   if n == 1:
    one = one   # one = 0
    two = ~two  # two = 0

已知位运算特性：

特性1：异或运算：x ^ 0 = x​ ， x ^ 1 = ~x
特性2：与运算：x & 0 = 0 ， x & 1 = x

观察可知：
a.当 two是1时，one不变
b.当 two是0时，入1则one取反，入0则one不变 （符合特性1: one = one^n）
（a,b符合特性2: one = (one^n) & ~two）
c.当 one变为0时，入1则two取反，入0则two不变（符合特性1：two = two^n）
d.当 one变为1时，two不变
（c,d符合特性2: two = (two^n) & ~one）

推导简化公式：

one = one ^ n & ~two
two = two ^ n & ~one

代码

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for(int num : nums){
            ones = ones ^ num & ~twos;
            twos = twos ^ num & ~ones;
        }
        return ones;
    }
}