题目：字符串中的第一个唯一字符
思路一：暴力查找，时间复杂度
思路一：开辟检查重复数组,以空间换时间，时间复杂度
这段代码的作用是在一个字符串 s 中找到第一个不重复（只出现一次）的字符，并返回它的下标。具体实现方式如下：
-
定义变量
i表示当前处理的字符下标，定义字符串rem表示已经检查过的字符集合。 -
使用
while循环遍历整个字符串，对于每个字符执行以下操作：a. 在该字符后面寻找与其相同的元素（即重复出现的元素），使用
s.find()函数实现，并将结果赋给变量pos1。b. 如果没找到重复元素，则表示当前字符为第一个不重复的字符，可以将其下标直接返回。
c. 如果找到了重复元素，在记录数组
rem中继续查找是否已经存在该字符，如果不存在，则将当前字符添加到rem中，也就是表示该字符已经被检查过了；否则，忽略该字符并继续向后查找。 -
如果遍历完整个字符串都没有找到不重复的字符，则返回 -1。
需要注意的是，这段代码中虽然使用了两个 find() 函数来查找字符，但是其时间复杂度仍为 O(n)，因为每个字符最多只会被处理两次。
实现：
class Solution {
public:
int firstUniqChar(string s)
{
//下标
int i = 0;
//记录数组
string rem;
while (i < s.size())
{
//查找它的相同元素
int pos1 = s.find(s[i], i + 1);
//没找到
if (pos1 == string::npos)
{
//对照一下记录数组是否含有该字符
int pos2 = rem.find(s[i], 0);
if (pos2 == string::npos)
{
return i;
}
else
{
i++;
}
}
//找到了
else
{
//记录该字符
rem += s[i];
//继续找下一个元素
i++;
}
}
return -1;
}
};思路三：计数排序
假设待排序的元素都是小写字母，那么我们可以考虑使用计数排序的思路来实现该算法。具体流程如下：
-
定义一个数组
alpha来表示每个小写字母出现的次数。由于小写字母一共有 26 个，所以数组大小为 26。 -
第一次遍历字符串
s，统计每个字符出现的次数，并将其存储到数组alpha中对应的位置上。 -
第二次遍历字符串
s，检查每个字符在数组alpha中对应的值是否为 1，如果是，则说明该字符是第一个不重复的字符。直接返回该字符的下标即可。文章来源：https://www.toymoban.com/news/detail-429502.html
这样做的时间复杂度也为 O(n)，但是它的空间复杂度仅为 O(1)（因为数组大小固定为 26）。但需要注意的是，该方法只适用于输入字符串仅包含小写字母的情况。文章来源地址https://www.toymoban.com/news/detail-429502.html
实现：
class Solution {
public:
int firstUniqChar(string s) {
int alpha[26] = {0};
for (char ch : s) {
alpha[ch - 'a']++;
}
for (int i = 0; i < s.length(); ++i) {
if (alpha[s[i] - 'a'] == 1) {
return i;
}
}
return -1;
}
};到了这里，关于字符串中的第一个唯一字符的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
