leetCode-137:Single Number II

问题描述

给定一个整数数组，里面有一个数字出现一次，其他数字出现三次，要求用 O(1) 的空间复杂度、O(n) 的时间复杂度将只出现一次的数字找出来。题目链接：**点我**

样例输入输出

输入：nums = [2,2,3,2]

输出：3

输入：nums = [0,1,0,1,0,1,99]

输出：99

问题解法

此题最简单是用一个 map 来存储数字出现的次数。但是这样不满足 O(1) 空间复杂度的要求。由于题目中除了某个数字外其他数字都出现 3 次，因此可以基于每个数字的二进制位进行统计，如果某个位置出现次数的余数不是 3 的整数倍，则说明这个位置是出现 1 次的数字对应的位置（即数字映射到当前位的数为 1），然后将每个位置的数进行或运算就能得到只出现一次的数字了。代码如下

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num : nums) {
                count += (num >> i) & 1;
            }

            if (count % 3 == 1) {
                result = result | (1 << i);
            }
        }

        return result;
    }
}