问题描述 链接到标题

137. 只出现一次的数字 II (Medium) 链接到标题

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

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

提示：

  • 1 <= nums.length <= 3 * 10⁴
  • -2³¹ <= nums[i] <= 2³¹ - 1
  • nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

解题思路 链接到标题

要想保证空间复杂度为 $O(1)$，我们需要考虑 nums 的二进制表示，即统计 nums[i] 的每一位上的数的和，由于只有一个元素出现一次，其他都出现了三次，那么我们对这个和 $ \mod 3$，得到的结果就是待找出的元素的每一位上的数。

代码 链接到标题 

class Solution {
  public:
    int singleNumber(vector<int> &nums) {
        vector<int> cnt(32);
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 32; ++j) {
                cnt[j] += ((nums[i] >> j) & 0x1);
            }
        }
        for (int i = 0; i < 32; ++i) {
        	cnt[i] = cnt[i] % 3;
        }
        int res = 0;
        for (int i = 0; i < 32; ++i) {
        	res |= (cnt[i] << i);	
        }
        return res;
    }
};