只出现一次的数字 II

试题来源：力扣（英文），力扣（中文）

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

Input:nums = [2,2,3,2]
Output: 3

Input:nums = [0,1,0,1,0,1,99]
Output: 99

问题分析：

前面我们讲过只出现一次的数字，只有一个数字出现一次，其他数字都出现两次，使用的是位运算解决。这题说的也是只有一个数字出现一次，但其他数字都出现 3 次。我们假设所有数字都出现 3 次，那么在 32 位二进制中每一位数字的和都能够被 3 整除，比如数组 [5,5,9,9,5,9] 。

我们看到 3 个 5 和 3 个 9 他们的二进制中每一位相加都能被 3 整除，如果再出现一个数字，那么就有可能（0除外）导致某些位上的数字相加之后不能被 3 整除，我们只需要根据每一位相加之后能不能被 3 整除，即可判断只出现一次数字的二进制在某个位置是否是 1 ，比如在上面数组中添加一个数字 6 。

public int singleNumber(int[] nums) {
    int res = 0;// 只出现一次的数字。
    // int类型有 32 位，统计每一位 1 的个数。
    for (int i = 0; i < 32; i++) {
        int oneCount = 0;//统计第 i 位中 1 的个数。
        for (int j = 0; j < nums.length; j++)
            oneCount += (nums[j] >>> i) & 1;
        // 如果 1 的个数不是 3 的倍数，说明只出现一次数字二进制位在这一位是 1。
        if (oneCount % 3 != 0)
            res |= 1 << i;
    }
    return res;
}

对于这题我们还可以扩展一下。
一，如果只有一个数字出现一次，其他数字都出现偶数次，只需要把所有数字异或一遍即可。
二，如果只有一个数字出现一次，其他数字都出现奇数次，可以用下面代码来解决。

// n是出现的次数。
public int singleElement(int[] nums, int n) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        int oneCount = 0;// 统计所有数字第 i 位中 1 的个数。
        // 统计每一位 1 的个数。
        for (int j = 0; j < nums.length; j++) {
            oneCount += (nums[j] >>> i) & 1;
        }
        // 判断每一位 1 的个数能不能被 n 整除。
        if (oneCount % n != 0)
            res |= (1 << i);
    }
    return res;
}

这题除了使用上面这种方式以外，我们还可以使用有限状态机。