137.只出现一次的数字 II

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

思路

为了找出在数组中仅出现一次的数字，同时实现线性时间复杂度和常数级空间复杂度，可以考虑使用位运算。我们利用每个数字在二进制位上的统计特性来达到这一目的。

1. 数组中的每个数都可以表示为一个固定长度（通常是 32 位）的二进制数。
2. 对于每一位上的所有数字的和（即二进制中所有数对应位上的求和），如果一个数字出现了三次，那么它们的每个位的和也会是 3 的倍数。
3. 因此，我们可以遍历每一位上的所有数字的和，将和对 3 取余，结果非零的位就属于只出现一次的那个数字。

• 时间复杂度:O(n)
• 空间复杂度:O(1)

代码

public static int singleNumber(int[] nums) {
    int[] count = new int[32];
    // 计算每一位上所有数字的和
    for (int num : nums) {
        for (int j = 0; j < 32; j++) {
            int numBit = num >> j;
            count[j] += numBit & 1;
        }
    }
    int result = 0;
    // 对每一位的计数对 3 取余，并重构单个出现的数
    for (int i = 0; i < 32; i++) {
        result += (count[i] % 3) << i;
    }
    return result;
}