哈希集合
开哈希集合，遍历字符串，未出现的字母加入哈希集合，如果字母出现过，返回这个字母即可。
创新互联建站专注于苍溪网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供苍溪营销型网站建设，苍溪网站制作、苍溪网页设计、苍溪网站官网定制、
微信小程序定制开发服务，打造苍溪网络公司原创品牌,更为您提供
苍溪网站排名全网营销落地服务。
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) ， 只使用常量级空间 。
AC
致语
- 理解思路很重要
- 读者有问题请留言，清墨看到就会回复的。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
标题名称：力扣(LeetCode)2351.第一个出现两次的字母(C++)-创新互联
网址分享：
http://cdkjz.cn/article/dsoodh.html
