只出现一次的数字 II

题目链接

只出现一次的数字 II

题目描述

注意点

• nums中，除某个元素仅出现一次外，其余每个元素都恰出现三次
• 设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题

解答思路

• 本题与只出现一次的数字的数字类似，区别是重复的数字会重复出现三次，仍然是通过位运算找到只出现一次的数字
• 对nums数组中的每个数字第i位进行加运算，加起来得到count，因为重复的数字会重复出现三次，所以需要对count模3取余，出现三次的数字该位为0，出现一次的数字该位为1，将每一位都做相同的运算后最终对每一位相加得到的就是只出现一次的数字

代码

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            // 统计第i位为1的数量
            int count = 0;
            for (int num : nums) {
                count += num >> i & 1;
            }
            res |= count % 3 << i;
        }
        return res;
    }
}

关键点

• 位运算的思想