z在一个数组$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

class Solution:
	def singleNumber(self, nums):

解题思路：

如下图所示，考虑数字的二进制形式，对于出现三次的数字，各二进制位出现的次数都是3的倍数。

因此，统计所有数字的各二进制中1的出现次数，并对3求余，结果则为只出现一次的数字。

方法一：有限状态自动机

各二进制位的位运算规则相同，因此只需考虑一位即可。如下图所示，对于所有数字中的某二进制1的个数，存在3种状态，即对3余数为0，1，2。

如下图所示，由于二进制只能表示0，1，因此需要使用两个二进制位来表示3个状态。设此两位分别为two，one，则状态转换变为：

00->01->10->00->…

接下来，需要通过状态转换表导出状态转换的计算公式。首先回忆以下位运算特点，对于任意二进制位$x$，有：

• 异或运算：$x^0=x, x^1=~x$
• 与运算：x & 0 = 0, x & 1 = x​

计算one方法：

设当前状态为two one，此时输入二进制位$n$。如下图所示，通过对状态表的情况拆分，可推出one的计算方法为：

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

class Solution:
	def singleNumber(self, nums):
		ones, twos = 0, 0
		for num in nums:
			ones = ones ^ num & ~twos
			twos = twos ^ num & ~ones
		return ones