广告联盟的网站怎么做,新乡做网站的公司,网站建设私单合同,平面设计岗位描述怎么写文章目录 Tag题目来源题目解读解题思路方法一#xff1a;位运算 写在最后 Tag
【位运算】【数组】【2023-10-15】 题目来源
137. 只出现一次的数字 II 题目解读
找出数组中仅出现一次的数字#xff0c;其余数字仅出现三次。要求线性时间复杂度求解。 解题思路
本题的朴素… 文章目录 Tag题目来源题目解读解题思路方法一位运算 写在最后 Tag
【位运算】【数组】【2023-10-15】 题目来源
137. 只出现一次的数字 II 题目解读
找出数组中仅出现一次的数字其余数字仅出现三次。要求线性时间复杂度求解。 解题思路
本题的朴素方法是利用哈希表统计数组中每个数字出现的次数出现的次数仅为 1 的那个数字是我们需要返回的答案。该方法的时间、空间复杂度均为 O ( n ) O(n) O(n)。
接下来将介绍一种空间复杂度为 O ( 1 ) O(1) O(1) 的位运算方法。
方法一位运算
数组中的int整型元素的范围是32位每一个32位的int整型数据都可以用32二进制来表示每一位上要么是 0 要么是 1。
我们遍历32位的每一个位 i统计数组中 i 位上的 0 或 1 的数量数组中的三个一样的数的这一位的 0 或 1 的数量一定是 3 的倍数如果此时统计的数组中 i 位上的 0 或 1 的数量是 3 的倍数还余 1那多出来的数量 1 一定是数组中仅出现一次的数称为答案的 i 位的数也就是说答案第 i 位为 1。
实现代码
class Solution {
public:int singleNumber(vectorint nums) {int res 0;for (int i 0; i 32; i) {int cnt 0;for (int num : nums) {cnt ((num i) 1);}if (cnt % 3) {res | (1 i);}}return res;}
};复杂度分析
时间复杂度 O ( n l o g C ) O(nlogC) O(nlogC) n n n 为数组 nums 的长度 C C C 是数据的范围本题中 l o g C 32 logC32 logC32。
空间复杂度 O ( 1 ) O(1) O(1)。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
