137. 只出现一次的数字 II(中等)twice

1，问题描述

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 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

2，初步思考

​ 位运算、门电路

3，代码处理

public class _137只出现一次的数字II {

    // 使用位运算
    public int singleNumber_bit(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int total = 0;
            for (int num : nums) {
                total += ((num >> i) & 1);// 获取num中第i位的值
            }
            if (total % 3 != 0) {// 求和
                ans |= (1 << i);
            }
        }
        return ans;
    }

    // 数字电路设计
    public int singleNumber_digital(int[] nums) {
        int a = 0, b = 0;
        for (int num : nums) {
            int aNext = (~a & b & num) | (a & ~b & ~num), bNext = ~a & (b ^ num);
            a = aNext;
            b = bNext;
        }
        return b;
    }


    public int singleNumber(int[] nums) {
        int a = 0, b = 0;
        for (int x : nums) {
            b = (b ^ x) & ~a;
            a = (a ^ x) & ~b;
        }
        return b;
    }

    public static void main(String[] args) {
        _137只出现一次的数字II onlyOne = new _137只出现一次的数字II();
        System.out.println(onlyOne.singleNumber(new int[]{-2, -2, 1, 1, 4, 1, 4, 4, -4, -2}));
    }
}