题目描述

在一个数组 $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$

---

算法

(位运算) $O(32n)$

枚举每个数的每一位，用 $one$ 记录每一位 $1$ 出现的个数，如果 one % 3 == 1 说明答案中的当前位是 $1$，否则 one % 3 == 0 说明答案中的当前位不是 $1$，只有这两种情况，因为剩下的数都出现了三次，只有答案是出现一次的数字，所以处理完每一位之后就可以得到答案，这个方法还是比较好理解的。

时间复杂度

枚举数字的每一位，每个数字 $32$ 位，总共 $n$ 个数，所以时间复杂度为 $O(32n)$，但这个算法其实不是 $O(n)$ 的，假设 n 的范围是 $10^6$，则 $ logn < 32 $，所以此算法时间复杂度是大于 $O(nlogn)$ 的。

空间复杂度

$O(1)$

C++ 代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < 32; i ++ ) {
            int one = 0;
            for (auto x : nums)
                if (x >> i & 1)
                    one ++ ;
            if (one % 3 == 1) res += (1 << i);
        }
        return res;
    }
};