【位运算】剑指offer 56. 数组中数字出现的次数
2022/4/29 23:47:31
本文主要是介绍【位运算】剑指offer 56. 数组中数字出现的次数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
这是一系列位运算的题目,本文将由浅入深,先从最简单的问题开始:
问题1:
一个数组中只有一个数字出现过1次,其余数字都出现过两次,请找到那个只出现1次的数字。要求时间复杂度是 \(O(n)\),空间复杂度是 \(O(1)\)。
解法:
考虑到位运算中的异或运算,一个数字和它自己做异或,结果为0。所以只需要遍历整个数组,挨个异或,最后得到的结果就是那个只出现1次的数字。
class Solution { public: vector<int> singleNumbers(vector<int>& nums) { int res = 0; for (auto num : nums) { res ^= num; } return res; } };
问题2:
一个整型数组
nums
里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 \(O(n)\),空间复杂度是 \(O(1)\)。
解法:
与问题 1 的区别在于,这个问题中有两个出现次数为 1 的数字。可以将数组分成两个子数组,每个子数组中各含一个只出现 1 次的数字。具体做法为:
- 对所有数字求异或,得到的结果即为
res
- 保留
res
中的一个为 1 的数位,其余数位都变成 0,可以用res & -res
保留最低位的 1,记为div
- 将数组中的每个数字和
div
做异或,按照结果为0或1分成2组,这样相同的数字都会被分到同一组,而那两个只出现 1 次的数字会被分到不同的组 - 按组再做异或,同问题1,得到答案。
实际操作中不需要真正分组,只需要用两个变量 a
和 b
记录两个组的异或值即可。
class Solution { public: vector<int> singleNumbers(vector<int>& nums) { int res = 0; for (auto num : nums) { res ^= num; } int a = 0, b = 0; int div = res & -res; for (auto num : nums) { if (div & num) { a ^= num; } else { b ^= num; } } return {a, b}; } };
问题3:
在一个数组
nums
中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。
解法:
参考:K神的题解
如下图所示,考虑数字的二进制形式,对于出现三次的数字,各二进制位 出现的次数都是 3 的倍数。因此,统计所有数字的各二进制位中 1 的出现次数,并对 3 求余,结果则为只出现一次的数字。
class Solution { public: int singleNumber(vector<int>& nums) { vector<int> digit(32); // 记录所有数字每个数位上1出现的次数之和 for (auto num : nums) { // 遍历每个数字 for (int i = 0; i < 32; i++) { // 遍历每个数位 digit[i] += num & 1; // num & 1 得到该数位是否为1 num >>= 1; // 获得下一个数位 } } int ans = 0, m = 3; for (int i = 31; i >= 0; i--) { //倒着遍历digigt数组,因为高数位在大下标位置 ans <<= 1; // ans左移1位 ans |= digit[31 - i] % m; // 每个数位对m取余后再和ans做或运算 } return ans; } };
上面的代码只需要修改求余数值 \(m\) ,即可实现解决除了一个数字之外,其余数字都出现 \(m\) 次的通用问题。
这篇关于【位运算】剑指offer 56. 数组中数字出现的次数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署