题目描述

在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。

请找出那个只出现一次的数字。

你可以假设满足条件的数字一定存在。

思考题：

• 如果要求只使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？

数据范围

数组长度 [1,1500]。

样例

输入：[1,1,1,2,2,2,3,4,4,4]
输出：3

方法一：状态机 O(n)

这道题是要找到只出现一次的那个数字，我们可以用位运算的思想，将数字用二进制表示拆分成 32 位（因为数据范围内数值最大也不会超过 32 位），将所有数字异或之后，如果每一位上为 1 出现的次数 %3 结果为 1 则说明只出现一次的那个数字在该位上为 1 ；如果 %3 结果为 0 ，则该数该位上为 0 。

因为其他数字出现了三次，所以同一个位置上如果有 1 的话就会出现三次，%3 就会得 0 。如果这时只出现一次的数在该位置上出现了 1 ，则 %3 就会多出一次来，从而进行区分。

所以这道题可以用类似于状态机的思想来做，需要用到 one 和 two 两个变量。按下面这个思路来，可以发现二进制位置上遇到 1 的时候按如下公式进行遇到 3 后又会得到开始的结果即循环一次周期为 3 ；而遇到 0 的话就会发生自环，即不会改变状态：

one = (one ^ x) & ~two

two = (two ^ x) & ~one

class Solution {
public:
    int findNumberAppearingOnce(vector<int>& nums) {
        int one = 0, two = 0;
        for (auto x : nums)
        {
            one = (one ^ x) & ~two;
            two = (two ^ x) & ~one;
        }
        return one;
    }
};

欢迎大家在评论区交流~