数组中数字出现的次数2

剑指 Offer 56 - II. 数组中数字出现的次数 II

难度中等122收藏分享切换为英文接收动态反馈

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

输入：nums = [3,4,3,3]
输出：4

示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：

• 1 <= nums.length <= 10000
• 1 <= nums[i] < 2^31

求每一位的数字

一个数组中某个元素只出现一次，其余数字出现m次，只需对每个数字的每一位求和，然后对每一位模m即可得到的每一位是只出现一次数字的每一位的数字

class Solution {
    public int singleNumber(int[] nums) {
        int[] count = new int[32];              //保存每一位数字的和的结果

        for (int num : nums) {                  //对于每个数字，求其每一位的和到count数组
            for (int i = 0; i < 32; i++) {
                count[i] += num & 1;
                num = num >>> 1;
            }
        }
        int res = 0, m = 3;
        for (int i = 0; i < 32; i++) {          //对每一位的数字求模m，得到单独出现的那个数字的每一位的数字
            res <<= 1;
            res |= count[31 - i] % m;           //恢复原来的只出现一次的数字
        }
        return res;
    }
}

参考文献

面试题56 - II. 数组中数字出现的次数 II（位运算 + 有限状态自动机，清晰图解）Krahets发布于 2020-04-23

赏

谢谢你请我吃糖果

微信