剑指 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

一、哈希表

哈希表的思路很简单，就是统计每个数字出现的次数，因为只有一个数字出现一次，其他都出现3次。代码如下：

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        //先把数字存储到map中，其中key存储的是当前数字，value是
        //数字的出现的次数
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //最后在遍历map中的所有元素，返回value值等于1的
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1)
                return entry.getKey();
        }
        return -1;
    }
}

二、有限状态自动机

首先回忆一下位运算特点，对于任意二进制位 xx ，有：

• 异或运算：x ^ 0 = x ， x ^ 1 = ~x
• 与运算：x & 0 = 0 ， x & 1 = x

再回忆一下：

取反运算符（~）
参加运算的一个数据，按二进制位进行“取反”运算。

运算规则：~1=0； ~0=1；

 即：对一个二进制数按位取反，即将0变1，1变0。

使一个数的最低位为零，可以表示为：a&~1。

~1的值为1111111111111110，再按“与”运算，最低位一定为0。因为 ~ 运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。

然后再放一下k神画的状态转化表的图：

个人想法是，建议看一下方法一，理解一下大概思路，然后在看这个方法。代码如下：

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;
    }
}

参考链接：

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/mian-shi-ti-56-ii-shu-zu-zhong-shu-zi-chu-xian-d-4/

https://blog.csdn.net/xiaopihaierletian/article/details/78162863