【LeetCode】137. 只出现一次的数字 II(剑指offer 56-II)

137. 只发生一次的数据 II(挥剑offer 56-II)

知识要点：哈希表；位运算

题型叙述

让你一个整数金额二维数组 nums ，除某一原素仅发生 一次 外，其他每一个原素都恰发生 三次 。你要找到并回到那一个只发生了一次的原素。

你的优化算法应当具备线形算法复杂度。 你能不应用附加室内空间来完成吗？

实例

键入：nums = [2,2,3,2]
輸出：3

键入：nums = [0,1,0,1,0,1,99]
輸出：99

打法一：HashMap

和136题一样，应用哈希表储存每一个数据发生的数据，再解析xml哈希表，看谁可以相当于1；
非常容易想起，但那样做的弊端便是必须 开拓新的室内空间；

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for(Integer i : nums){
            map.put(i, map.getOrDefault(i, 0) 1);
        }
        for(Integer i: map.keySet()){
            if(map.get(i) == 1) return i;
        }
        return -1;
    }
}

算法复杂度：O(N);
空间复杂度：O(N);

打法二：位运算

这题不可以再用异或运算去解了，由于变成了三个没有办法相抵，可是想像一下，如果有三个一模一样的数据，那这三个数据二进制求和后，全部位上要不是0；要不都是3的倍数；随后大家的不必要原素，要不再加上去为0；要不再加上去多了一个1，因此能够 先后求每一位的和，随后%3，假如数值1，那证实我们在这名上的数值1；不然为0；
如下图所显示；

class Solution {
    public int singleNumber(int[] nums) {
        //在java中int类型是32位系统，大家必须 统计分析全部数据在某一部位的和能否被3整除，
        // 假如不可以被3整除，表明那一个只发生一次的数据的二进制在那一个部位是1……把32位系统所有统计分析完截止
        int ans = 0;
        for(int i = 0; i < 32; i  ){
            int count = 0; //统计分析1的数量；
            for(int j = 0; j < nums.length; j  ){
                count  = (nums[j] >> i) & 1; //统计分析全部数在第i位上1的数量；
            }
            if(count % 3 != 0){
                ans = ans | (1 << i); //别的位不会改变，第i部位为1；
            }
        }
        return ans;
    }
}

算法复杂度：O(N);
空间复杂度：O(1);

感受

**把握位运算的解决方案：这类题型通常要按位与、按位异或等实际操作；
除此之外还会继续有偏移<<;偏移>>等；例如：

a & 1 ： a的别的位全为0，最终一位不会改变：即取a最终一位；
a | (1 << i) : a的别的位不会改变，把a的第i部位为1；
(a >> i) & 1 : 取下a第i位上的值；