力扣(LeetCode)2351.第一个出现两次的字母(C++)-创新互联
哈希集合
当前文章:力扣(LeetCode)2351.第一个出现两次的字母(C++)-创新互联
转载来源:http://myzitong.com/article/dsoodh.html
开哈希集合,遍历字符串,未出现的字母加入哈希集合,如果字母出现过,返回这个字母即可。
创新互联建站专注于苍溪网站建设服务及定制,我们拥有丰富的企业做网站经验。 热诚为您提供苍溪营销型网站建设,苍溪网站制作、苍溪网页设计、苍溪网站官网定制、微信小程序定制开发服务,打造苍溪网络公司原创品牌,更为您提供苍溪网站排名全网营销落地服务。class Solution {public:
char repeatedCharacter(string s) {unordered_setS;
for(auto &c:s)
if(!S.count(c)) S.insert(c);
else return c;
return 0;
}
};
- 时间复杂度 : O ( n ) O(n) O(n) , n n n 是字母数量,遍历每个字母一次,时间复杂度 O ( n ) O(n) O(n) 。
- 空间复杂度 : O ( ∣ C ∣ ) O(|C|) O(∣C∣) , 字符集的大小 ∣ C ∣ = 26 |C|= 26 ∣C∣=26 ,哈希集合的空间复杂度 O ( ∣ C ∣ ) O(|C|) O(∣C∣) 。
字符集一共26
个字母,整型数有1
位符号位、31
位数字位,利用数字位,最多可以表示31
个不同的字符。数字位是1
表示有这一位,0
表示没有这一位。一次遍历字符串,利用位运算,将字母对应到数字位。当前位是0
,变为1
;当前位是1
,返回这个字母即可。
提示 : 位运算小技巧i>>j&1
——i
表示存储位运算的数字,j
表示i
的第j
位。i>>j&1
检查i
的第j
位是不是1
。
class Solution {public:
char repeatedCharacter(string s) {int ans = 0;
for(auto &c:s){if(ans>>c-'a'&1) return c;
ans |= 1<
- 时间复杂度 : O ( n ) O(n) O(n) , n n n 是字母数量,遍历每个字母一次,时间复杂度 O ( n ) O(n) O(n) 。
- 空间复杂度 : O ( 1 ) O(1) O(1) , 只使用常量级空间 。
- 理解思路很重要
- 读者有问题请留言,清墨看到就会回复的。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
当前文章:力扣(LeetCode)2351.第一个出现两次的字母(C++)-创新互联
转载来源:http://myzitong.com/article/dsoodh.html