在一个数组 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分析：
方法1：哈希表
这题没有了I、数组中数字出现的次数 时间空间复杂度的限制，那么就可以用哈希表的方式存储每一个数字出现的次数，最后遍历哈希表，返回出现次数为 1 的数字。
时间复杂度：O(n)
空间复杂度：O(n)
class Solution { public int singleNumber(int[] nums) { //定义哈希表存储每个数出现的次数 HashMap
方法2：位运算
因为除了某个数其他数都出现了三次，因此这些数二进制每位相加一定为 3 的倍数，那么只需要把所有数的每一位加起来取余 3 就是那个只出现一次的数。
时间复杂度：O(n * C) C 为 32
空间复杂度：O(1)
class Solution { public int singleNumber(int[] nums) { //记录每位出现的次数，以及位数，结果 int count = 0, digit = 1, sum = 0; //遍历记录每位 1 的个数 for(int i = 0; i < 32; ++i){ for(int n: nums){ if((n & digit) == digit){ count++; } } //记录结果 sum += count % 3 * digit; //移到下一位 digit <<= 1; //重置次数 count = 0; } return sum; }}
方法3：有限状态机
由 方法2 可以知道，只出现一次的数字的每一位都所有数字的每一位相加 取余 3 的结果，那么没加一位数字，余数就有三种状态：0，1，2，加入二进制 0 ，状态不变，加入二进制 1，状态按照 0 → 1 → 2 → 0 的方式进行改变，按照该方式相加到最后的结果就是我们需要的数字。但是，余数有三种状态，二进制只有 0，1两种，所以需要俩个二进制来表示，即 00，01，10，第一位表令为 a，第二位令为 b，那么 a，b 满足以下条件：
对 a：
当加入 0 时，若 b 为 0，a 不变；若 b 为 1，a 不变且必为 0当加入 1 时，若 b 为 0，a 取反；若 b 为 1，a 为 0
对 b：
当加入 0 时，若 a 为 0，b 不变且必为 1；若 a 为 1，b 不变当加入 1 时，若 a 为 0，b 为 0；若 a 为 1，b 为 1（取反）
由异或运算和与运算可知：
x ^ 0 = x，x ^ 1 = ~xx & 0 = 0，x & 1 = x
那么a，b可化为：
对 a：
a = a ^ n & ~b
对 b：b 化不了，但可以在化过的 a 基础上化：
当加入 0 时，若 a 为 0，b 不变；若 a 为 1，b 不变且必为 0当加入 1 时，若 a 为 0，b 取反；若 a 为 1，b 为 0
即：
b = b ^ n & ~a
因为最后的结果余数必为 0 或 1，所以 a 即为最终答案。
时间复杂度：O(n)
空间复杂度：O(1)
class Solution { public int singleNumber(int[] nums) { //定义状态数的位数 int a = 0, b = 0; //遍历 for(int n: nums){ a = a ^ n & ~b; b = b ^ n & ~a; } return a; }}
题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof