网站外包注意事项,建设青岛公司网站,网页设计的网站推荐,做维修注册网站给你一个整数数组 nums #xff0c;除某个元素仅出现 一次 外#xff0c;其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。 常规解法#xff1a;哈希#xff08;hash#xff09; …给你一个整数数组 nums 除某个元素仅出现 一次 外其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。 常规解法哈希hash
使用哈希映射统计数组中每个元素的出现次数对于哈希映射中的每个键值对键表示一个元素值表示其出现的次数。在统计完成后遍历哈希映射即可找出只出现一次的元素
class Solution {
public:// 哈希表int singleNumber(vectorint nums) {unordered_mapint,int mp;for(const int num:nums) {mp[num];}int ans 0;// for(auto it:mp) // if(it.second1) return it.first;for(auto [x,cnt]:mp) if(cnt1) {ansx;break;}return ans;}
};
时间复杂度O(n)其中 n 是数组的长度。空间复杂度O(n)哈希映射中包含最多 ⌊n/3⌋1 个元素即需要的空间为 O(n)
****************************************** 进入本文正题****************************************** 1实现「统计每个比特位的 1 的个数」 class Solution {
public:// 模3加法 方法1统计每个比特位的1的个数int singleNumber(vectorint nums) {int ans 0 ;for(int i0;i32;i) {int cnt 0;for(const int x : nums) {cnt (xi 1);}ans | (cnt%3) i;}return ans;}
};
2位运算设计 模3加法器 可以使用一个「黑盒」存储当前遍历过的所有整数「黑盒」的第 i 位为{ 0, 1, 2 }三者之一表示当前遍历过的所有整数的第 i 位之和除以3的余数。但由于二进制表示中只有 0 和 1 而没有 2因此我们可以考虑在「黑盒」中使用两个整数来进行存储即
黑盒中存储了两个整数 a 和 b且会有三种情况
a 的第 位为 0 且 b 的第 位为 0表示 0a 的第 位为 0 且 b 的第 位为 1表示 1a 的第 位为 1 且 b 的第 位为 0表示 2
当遍历到一个新的整数 时对于 的第 位
如果 0那么 a 和 b 的第 位不变如果 1那么 a 和 b 的第 位按照 (00) - (01) - (10) - (00) 这一循环进行变化
分析本题思路和 single Number 一样同样考虑一个比特位的情况这里需要对这个比特进行计数到 3 时归 0也就是说需要一个模3加法器。但是没有现成的加法器那么需要自己构造一个能位运算的模3加法器
思考计数器要经历 0,1,2 这三个状态但是一个比特位只能表示两个状态怎么办呢此时我们可以扩展一个比特即用两个比特来保存位计数器的三个状态。假设 b 为低位, a 为高位。c 代表 的第 位:用 ab 两个比特位来作为这一位 c 的位计数器。
当这一位 c 来 1 时位计数器就进行状态转换否则维持原状态而最后的结果会保存在计算器的低位 b 里当 c 为 0 时不会变化那么状态不发生变化
注a1 和 b1 表示 ab 的下一个状态 ,c 代表 的第 位:, 表示 a非 表示 b非
1.「同时计算」 转成代码
a (~a b c) | (a ~b ~c)b (~a) (b ^ c)
C代码
class Solution {
public:// 模3加法 方法2用位运算实现int singleNumber(vectorint nums) {int a0,b0;for(const int x:nums) {int tmp_a a;a (a^x) (a|b);b (b^x) (~tmp_a);}return b; }
};
2.「分别计算」
发现「同时计算」中计算 b 的规则较为简单而 a 的规则较为麻烦可改为「分别计算」即先计算出 b再拿新的 b 值计算 a 转成代码
b (~a) (b ^ c) // 所以,先计算出ba (~b) (a ^ c) // 再计算a
C代码
class Solution {
public:// 模3加法 方法2用位运算实现int singleNumber(vectorint nums) {int a0,b0;for(const int x:nums) {b (b^x) (~a);a (a^x) (~b);}return b; }
};
时间复杂度O(n)其中 n 为 nums 的长度空间复杂度O(1)仅用到若干额外变量
3有限状态自动机
对于异或模2加法来说把一个数不断地异或1相当于在 0 和 1 之间不断转换即 0-1-0-1-... 类似地模 3 加法 就是在 0, 1, 2, 之间不断转换即 0-1-2-0-1-2-... 当 a 0 且 b 0 时a 必须保持不变仍然为 0当 a 1 时此时 b 一定是 0必须保持不变仍然为 0
【注】 代表 的第 位 : , 表示 a非 表示 b非
if(a 0) {if(c 0) {bb;}if(c 1) {b~b;}
}if(a 1) {b0;
}
引入异或运算当 if(a 0) 时 转成代码:
if(a 0) b b ^ c;
那么可以将上述拆分简化为
if(a 0) b b ^ c;
if(a 1) b 0;
引入与运算,继续简化: 转成代码:
b (~a) (b ^ c); a (~b) (a ^ c);
推荐和参考文章
137. 只出现一次的数字 II - 力扣LeetCodehttps://leetcode.cn/problems/single-number-ii/solutions/2482832/dai-ni-yi-bu-bu-tui-dao-chu-wei-yun-suan-wnwy/137. 只出现一次的数字 II - 力扣LeetCodehttps://leetcode.cn/problems/single-number-ii/solutions/8944/single-number-ii-mo-ni-san-jin-zhi-fa-by-jin407891/137. 只出现一次的数字 II - 力扣LeetCodehttps://leetcode.cn/problems/single-number-ii/solutions/746993/zhi-chu-xian-yi-ci-de-shu-zi-ii-by-leetc-23t6/
[LeetCode]Single Number, Single Number II Single Number III - J坚持C - 博客园 (cnblogs.com)https://www.cnblogs.com/wf751620780/p/10730758.html
