剑指 Offer 56 - I. 数组中数字出现的次数
2022/2/5 6:12:33
本文主要是介绍剑指 Offer 56 - I. 数组中数字出现的次数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
剑指 Offer 56 - I. 数组中数字出现的次数
最容易想到的办法自然是哈希计数,但是我们发现题目的范围给到了\(1e5\),不断的给哈希表扩容比较花时间,也需要\(O(n)\)的遍历时间,还需要开哈希表的\(O(n)\)空间。
class Solution { public int[] singleNumbers(int[] nums) { int[] res = new int[2]; Map<Integer, Integer> map = new HashMap<>(); for(var num : nums) { map.put(num, map.getOrDefault(num, 0) + 1); } int idx = 0; for(var key : map.keySet()) { if(map.get(key) == 1) { res[idx++] = key; } } return res; } }
再接着考虑原地空间的方式,这时就需要注意到其他数字都出现了2次,由异或的知识可以知道\(n \text{^} n = 0\)且\(0 \text{^} n = n\)。
因此我们先枚举一趟\(nums\),从\(0\)开始异或每一个\(num\),如果出现过两次的就会相互消去,只出现过1次的那两个数字a,b得到了它们异或的结果\(n = a \text{^} b\)。
此时我们还是无法确定\(a\)和\(b\)的,需要再想到我们求得\(n\)的最右边那位1设这位索引位置为\(i\),得到此时的值\(n = n \text{&} (-n)\)。
可以比较容易的得到\(a_2\)的第\(i\)位和\(b_2\)的第\(i\)位显然一个为1,一个为0,因此总能得到a和b。
class Solution { public int[] singleNumbers(int[] nums) { int n = 0; for(var num : nums) { n ^= num; } n &= -n; int[] res = new int[2]; for(var num : nums) { if((num & n) != 0) { res[0] ^= num; } else { res[1] ^= num; } } return res; } }
这篇关于剑指 Offer 56 - I. 数组中数字出现的次数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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登录鉴权入门:打造安全的用户认证系统