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

原题：点击此处

考点：位运算

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

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

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;
    }
}

编程易错点：

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

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

最后

以上就是含糊信封为你收集整理的剑指Offer：数组中数字出现的次数 II（JAVA实现）的全部内容，希望文章能够帮你解决剑指Offer：数组中数字出现的次数 II（JAVA实现）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。