题目链接

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

---

分析：
这题不像上一题，出现两次直接异或就抵消了，异或三次结果和异或一次是一样的。
可以采用状态机的思想，用两个变量one two

1. 当数字x的某一位是1并且出现一次，one的对应位变1，two的对应位为0
2. 当数字x的某一位是1并且出现两次，one的对应位变0，two的对应位变1
3. 当数字x的某一位是1并且出现三次，one和two的对应位都变回0

总结的式子就是下面代码，这式子自己想太难了，我选择哈希表

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