剑指Offer：数组中数字出现的次数 II（JAVA实现）

109 阅读 0 评论 72 点赞

我是靠谱客的博主含糊信封，这篇文章主要介绍剑指Offer：数组中数字出现的次数 II（JAVA实现），现在分享给大家，希望可以做个参考。

原题：点击此处

考点：位运算

本题与上一题相比，明显有混淆之意。
这一题中数字出现了3次，因此异或就没有可用之处了，因为异或3次本身还是自己。

本题的关键是：
在二进制位中，如果出现了3次的位置，必定是3的倍数，因此对该位置进行余3操作，剩余的值便是唯一一个出现1次的数字在该位置的数字

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int singleNumber(int[] nums) {
        int[] bitNums = new int[32];
        Arrays.fill(bitNums,0);
        for(int num:nums){
            int curBit = 1;
            for(int i = 31;i>=0;i--){
                if((curBit & num) == curBit){
                    bitNums[i]++;
                }
                curBit <<= 1;
            }
        }
        int result = 0;
        for(int i = 0;i<32; i++){
            result = result << 1;
            result += (bitNums[i]%3);
        }
        return result;
    }
}

编程易错点：

第一个for循环要从31到0开始记录，第二个循环要从0到31进行记录，因为第二个循环中的result是不断进行左移的。
在第一个循环中(curBit & num) == curBit不要写成了(curBit & num) == 1
在第二个循环中result = result << 1;一定要写在result += (bitNums[i]%3);的前面，不这样写的话，后面会多左移一次。

本题空间复杂度为O（1），因为数组是32位的常数级别。
时间复杂度为O（n）