剑指56-II：数组中数字出现的次数II

传送门

leetcode

题目描述

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

C++ 代码 - leetcode

/*
    如果某个数字出现 3 次，三数寨之和肯定能被 3 整除，则其对应二进制位的每一位之和也能被 3 整除。
    统计数组中每个数字表示二进制中每一位的和，判断该数是否能被 3 整除。
    若可以，则只出现一次的数字二进制数中那一位为 0；否则，其二进制数中那一位为 1。
*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < 32; i ++) {
            int cnt = 0;
            for (int x : nums) {
                if (x & (1 << i)) {
                    cnt ++;
                }
            }
            if (cnt % 3 == 1) {
                res ^= (1 << i);
            }
        }

        return res;
    }
};