力扣---137. 只出现一次的数字 II

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

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

示例 1：

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

示例 2：

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

提示：

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

可以想到的是，所有数字的每一位进行累加，答案对应等于 0 的位置 1 出现次数是 3 的倍数。

可以用一个32 的数组来模拟答案，将 nums 中所有元素中每一个 1 放到数组中，最后对数组中所有元素对 3 取余，剩下的 0 和 1 就是答案的二进制。

class Solution {
    public int singleNumber(int[] nums) {
        int[] ans = new int[32];
        for (int x : nums) {
            int temp = 1;
            // 遍历获取每一位的字母
            for (int i = 0; i < 32; i++) {
                int tem = (x & temp);
                int temp1 = 1;
                // 如果不等于 0，则说明 x 的第 i 位是 1
                if (tem != 0) {
                    ans[i]++;
                }
                temp <<= 1;
            }
        }
        int res = 0;
        // 将模拟数组转为数字
        for (int i = 0; i < 32; i++) {
            int x = ans[i];
            x %= 3;
            if (x == 1) {
                int temp = 1;
                temp <<= i;
                res ^= temp;
            }
        }
        return res;
    }
}

 每次计算完每一位后进行下一位的计算，优化。

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        int temp = 1;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int x : nums) {
                if ((x & temp) == temp) {
                    count ++;
                }
            }
            if (count % 3 == 1) {
                res ^= temp;
            }
            temp <<= 1;
        }
        return res;
    }
}