侧边栏壁纸
博主头像
landery博主等级

行李箱里装不下我想去的远方

  • 累计撰写 45 篇文章
  • 累计创建 26 个标签
  • 累计收到 6 条评论

目 录CONTENT

文章目录

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

landery
2022-10-31 / 0 评论 / 0 点赞 / 86 阅读 / 625 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-10-31,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

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

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

示例 1:

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

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

提示:

1<=nums.length<=31041 <= nums.length <= 3*10^4
231<=nums[i]<=2311-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

0

评论区