title: Leecode-剑指 Offer II 004. 只出现一次的数字 date: 2022-10-31 10:50:21.266 updated: 2022-10-31 10:50:21.266 url: /archives/leecode--jian-zhi-offerii004-zhi-chu-xian-yi-ci-de-shu-zi categories:

  • leecode tags:

  • leecode

剑指 Offer II 004. 只出现一次的数字

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

示例 1：

输入：nums = [2,2,3,2] 输出：3 示例 2：

输入：nums = [0,1,0,1,0,1,100] 输出：100

提示：

​ $1 <= nums.length <= 3*10^4$​ $-2^{31} <= nums[i] <= 2^{31} - 1$ nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

解法一：直接暴力了

直接使用一个HashMap来存谁出现过，统计出先超过三次的直接移除，最后剩下的就是结果：

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer,Integer> mmap = new HashMap();
        for(int i = 0 ;i < nums.length; i++){
            if(!mmap.containsKey(nums[i])){
                mmap.put(nums[i],1);
                continue;
            }
            
            if(mmap.containsKey(nums[i])){
                if(mmap.get(nums[i])+1 == 3){
                    mmap.remove(nums[i]);
                    continue;
                }
                mmap.put(nums[i],mmap.get(nums[i])+1); 
            }
        }
        
        List<Integer> ls=new ArrayList(mmap.keySet());
        return ls.get(0);
    }
}

但结果显然不太好：

image-1667184433585

解法二

思路：将数组中每一个数转为二进制数放到数组中，然后依次相加，计算所有数的各个位上的和，因为题目要求数组肯定是重复的是3个，剩下的是一个，那么各数位对3取模，只有0和1两种情况，最后对3取模后，相同的数字就被消掉了--各数位变为0，然后再将二进制转为十进制即可。

class Solution {
    public int singleNumber(int[] nums) {
        //java的int整型为32位
        int[] arr=new int[32];
        for(int num:nums){
            for(int i=0;i<32;i++){
                arr[i]+=(num>>(31-i))&1;
            }
        }
        int res=0;
        for(int i=0;i<32;i++){
            res=(res<<1)+arr[i]%3;
        }
        return res;
    }
}

image-1667184446528

当然同样的思路，优化一下写法，省去了数组的操作时间与空间：

class Solution {
     public int singleNumber(int[] nums) {
        int res = 0;
        for(int i = 0; i < 32; i ++) {
            int tmp = 0;
            for(int num : nums) {
                tmp += (num >> i) & 1;
            }
            res |= (tmp % 3) << i;
        }
        return res;
    }
}
其他思路

利用java 8新特性：

class Solution {
     public int singleNumber(int[] nums) {
        return Arrays.stream(nums).boxed().collect(Collectors.groupingBy(Integer::intValue)).values().stream().filter(list -> list.size() == 1).findFirst().get().get(0);
    }
}

但效果不太理想。

image-1667184459606