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

示例 1：
输入：nums = [2,2,3,2]
输出：3

示例 2：
输入：nums = [0,1,0,1,0,1,100]
输出：100

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

进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

注意：本题与主站 137 题相同：https://leetcode-cn.com/problems/single-number-ii/

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/WGki4K
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路及方法

最简单的方法是用map计数，但是没有啥意义。HashMap虽然是O(n)，但是空间也是O(n)，所以用位运算。对于出现三次的数来说，它的二进制位第i位要么出现3次0，要么出现3次1，即出现次数都是3的倍数。如果哪一位出现次数不是3的倍数，说明当前位被只出现一次的数，即答案数影响，记录当前位。

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;

        for (int i = 0; i < 32; i++) {
            // 记录当前第i位所有数为1的次数
            int cnt = 0;
            for (int num : nums) {
                cnt += (num >> i) & 1;
            }

            // 出现次数不是3的倍数，即代表答案数当前位为1
            if (cnt % 3 != 0) {
                res |= (1 << i);
            }
        }

        return res;
    }
}

结果如下：