题目描述

描述转载自力扣《137. 只出现一次的数字 II》

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

示例1

输入:nums = [2,2,3,2]
输出:3

示例2

输入:nums = [0,1,0,1,0,1,99]
输出:99

解题思路

  1. 将所有数字的二进制对应位置进行求和,用过 Excel 的胖友应该都知道求和操作,如图
    图片说明
  2. 因为有 3 个数是重复的,所有把所有二进制位求和之后得到的数值进行取模操作,如图
    图片说明
    于是就得到了结果。

Java代码实现

class Solution {
    public int singleNumber(int[] nums) {
        int[] count = new int[32];
        for (int i = 0; i < nums.length; ++i) {
            for (int j = 0; j < 32; ++j) {
                count[j] += nums[i] & 1;
                nums[i] >>>= 1;
            }
        }

        int res = 0;
        for (int i = 0; i < 32; ++i) {
            res <<= 1;
            res |= count[31 - i] % 3;
        }


        return res;
    }
}