剑指 Offer 56 - II. 数组中数字出现的次数 II
2022/2/5 6:12:35
本文主要是介绍剑指 Offer 56 - II. 数组中数字出现的次数 II,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
剑指 Offer 56 - II. 数组中数字出现的次数 II
最容易想到的自然还是map计数
class Solution { public int singleNumber(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for(var num : nums) { map.put(num, map.getOrDefault(num, 0) + 1); } for(var num : map.keySet()) { if(map.get(num) == 1) { return num; } } return 0; } }
时间复杂度为\(O(n)\),空间复杂度为\(O(n)\),其中时间复杂度可能要超过\(O(n)\),其中包括哈希表的扩容操作。
这里的运用位运算的方法我属实是想不太来,这里用了一个32位的数组来计算每一个二进制位出现的次数,如果一个数字出现了3次,那么它的每一位肯定也是出现了3次的,所以我们枚举每一个数字,将每个数字的二进制位出现的次数更新,再遍历\(map\)数组,如果\(map[i]\)出现的次数不是3的倍数,那么这一位肯定就是单独的那个数字中的,我们将每一位的位权相加即可。
class Solution { public int singleNumber(int[] nums) { int[] map = new int[32]; for(var num : nums) { for(int i = 0; i < 32; i++) { map[i] += (num & 1); num >>= 1; } } int res = 0; for(int i = 31; i >= 0; i--) { res = res << 1; if(map[i] % 3 == 1) { res |= 1; } } return res; } }
这篇关于剑指 Offer 56 - II. 数组中数字出现的次数 II的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-20接口模块封装入门教程
- 2024-09-20请求动作封装入门教程
- 2024-09-20登录鉴权学习:新手入门教程
- 2024-09-20后台管理开发学习:新手入门指南
- 2024-09-20后台管理系统开发学习:从入门到实践
- 2024-09-20后台开发学习:从入门到初级实战指南
- 2024-09-20后台综合解决方案学习:从入门到实践
- 2024-09-20接口模块封装学习入门指南
- 2024-09-20请求动作封装学习:新手入门教程
- 2024-09-20登录鉴权入门:打造安全的用户认证系统