网站怎么做房源,mvc5网站开发之六,网页制作培训班哪个好,wordpress 裁剪图片上传个人主页#xff1a;C忠实粉丝 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 C忠实粉丝 原创 位运算(6)_只出现一次的数字 II 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记#xff0c;欢迎大家在评论区交流讨论#x1f48c; 目录 … 个人主页C忠实粉丝 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 C忠实粉丝 原创 位运算(6)_只出现一次的数字 II 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记欢迎大家在评论区交流讨论 目录 温馨提示:
1. 题目链接 :
2. 题目描述 :
3. 解法(位运算) : 算法思路 : 代码展示 : 结果分析 : 温馨提示:
本文的算法题需要一些位运算知识的基础,如果大家还不是很了解的话,可以先去看下面的博客:位运算(1)_常见位运算总结-CSDN博客
1. 题目链接 :
OJ链接: 只出现一次的数字 II
2. 题目描述 :
给你一个整数数组 nums 除某个元素仅出现 一次 外其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
(也就是时间复杂度为O(N),空间复杂度为O(1))
示例 1
输入nums [2,2,3,2]
输出3示例 2
输入nums [0,1,0,1,0,1,99]
输出99提示
1 nums.length 3 * 104-231 nums[i] 231 - 1nums 中除某个元素仅出现 一次 外其余每个元素都恰出现 三次
3. 解法(位运算) : 算法思路 : 设要找的数位ret. 由于整个数组中,需要找的元素只出现了[一次],其余的数都出现了三次,因此我们可以根据所有数的[某一个比特位]的总和%3的结果,快速定位到ret的[一个比特位上]的值是0还是1. 这样我们通过ret的每一个比特位上的值,就可以将ret给还原出来. 代码展示 :
class Solution {
public:int singleNumber(vectorint nums) {int ret 0;for(int i 0; i 32; i){int sum 0;for(auto ch : nums)if(((ch i) 1) 1) sum;if(sum % 3) ret | 1 i;}return ret;}
}; 整体思路: 位操作 : 利用位操作和位的统计方法来解决问题。每个数字都是由 32 位组成遍历每一位并统计所有数字在该位上为 1 的次数。 模运算 : 通过 sum % 3 来确定在这个位上是否只出现了一次的数字。如果该位的 1 的出现次数不为 3则该位的值应该在结果中保留。 结果分析 : 时间复杂度: 外层循环遍历 32 位O(32), 也就是 O(1)。 内层循环遍历数组 nums假设数组的长度为 n则内层的复杂度为 O(n)。 总的时间复杂度为 O(n)。空间复杂度 : 只使用了常数级别的额外空间ret, sum, 和循环变量所以空间复杂度为 O(1)。
