描述

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

示例

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

提示

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

解题思路

对于数组中非答案的元素，每一个元素都出现了 3 次，对应着第 i 个二进制位的 3 个 0 或 3 个 1，无论是哪一种情况，它们的和都是 3 的倍数（即和为 0 或 3）。因此：
答案的第 i 个二进制位就是数组中所有元素的第 i 个二进制位之和除以 3 的余数。
对于数组中的每一个元素 x，我们使用位运算 (x >> i) & 1 得到 x 的第 i 个二进制位，并将它们相加再对 3 取余，得到的结果一定为 0 或 1，即为答案的第 i 个二进制位。

代码

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int total = 0;
            for (int num: nums) {
                total += ((num >> i) & 1);
            }
            if (total % 3 != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
}