一、题目

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

点击查看原题

二、思路

该题的简单版本是每个元素都出现两次，只有一个元素出现一次，使用异或操作，相同位会消去成为0，就可以筛选出出现一次的元素。
而现在的题目是每个元素都会出现三次，奇数次数就无法使用异或的操作来处理。可以考虑以下方法：

1）暴力解法-哈希表

使用一个HashMap，以元素作为键记录元素出现过的次数。然后遍历HashMap，找到出现次数为一次的那个元素。

2）对元素每个位进行统计

元素位32位，由于重复元素出现的次数是3次，则同一位上出现1的次数是3的倍数（如：3->0000 0000 0000 0000 0000 0000 0000 0011，低位的第一和第二位出现次数一定是3次），就算是加上其他不同值重复元素同样位的次数，也是3的倍数。
那么现在考虑把单独那个元素的位加进去，单独元素的各位出现1的情况，会让统计位为1的次数无法被3整除，这样就可以以此复原单独元素的值。

3）有限状态自动机

其实可以将元素出现3次认定为3个状态，使用两个变量one和two来代表，(two, one)的单个位上的状态可以认定为：(0, 0)->(0, 1)->(1, 0)，这三个状态周而复始，也就是出现三次的元素状态记录会归零，而出现一次的状态会记录在one中，也就符合简单版本题目的思想。
当需要记录的位为0时：

(two, one)：（0，0）->（0，0） (two, one)：（0，1）->（0，1） (two, one)：（1，0）->（1，0）

当需要记录的位为1时：

(two, one)：（0，0）->（0，1） (two, one)：（0，1）->（1，0） (two, one)：（1，0）->（0，0）

设需要记录位的值为x，可以得到公式：，更新完one后，根据更新后one的值来更新two，可以根据上面的表示得到：。

三、代码

1）暴力解法-哈希表

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap();
        for (int i : nums) {
            if (map.containsKey(i)) {
                map.put(i, map.get(i) + 1);
            } else {
                map.put(i, 1);
            }
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return 0;
    }
}

该方法时间复杂度为，空间复杂度为。

2）对元素每个位进行统计

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int total = 0;
            for (int num : nums) {
                total += ((num >> i) & 1);    // 统计从低->高，所有元素第i位上1出现的次数
            }
            if (total % 3 == 1) {
                ans |= (1 << i);    // 根据偏移量i来复原单独出现的元素
            }
        }
        return ans;
    }
}

该方法时间复杂度为，空间复杂度为。

3）有限状态自动机

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

该方法时间复杂度为，空间复杂度为。