问题描述
给定一个字符串 s
,找到 它的第一个不重复的字符,并返回它的索引 。如果不存在,则返回 -1
。
示例 1:
输入: s = "leetcode" 输出: 0
示例 2:
输入: s = "loveleetcode" 输出: 2
示例 3:
输入: s = "aabb" 输出: -1
提示:
1 <= s.length <= 105
s
只包含小写字母
思路
对于这种题目,我们通常会有至少两种思路。
思路一:暴力求解,反复遍历数组,找出单个的值,但是时间复杂度是N^2,消耗巨大。
思路二:借助基数排序(计数排序)的思想,不去关注元素,而是关注元素的数目。
下面是思路二的步骤:
1.新建一个int类型的数组,用于映射字符的相对位置。由于只包含小写字符,容量开到26就可以。否则需要开256(-128到127或0-255)个空间。
2.进行相对映射,完成统计数目。
3.再次遍历原数组,返回索引。
代码
class Solution {
public:
int firstUniqChar(string s) {
int CountA[26] = { 0 }; //初始化为0,计数数组,int类型
// 计数
for (auto ch : s)
{
CountA[ch - 'a']++; //相对映射
}
//返回
for (int i = 0; i < s.size(); i++)
{
if (CountA[s[i] - 'a'] == 1)
return i;
}
return -1;
}
};
//关键的 : 注意相对映射的下标
需要注意的是,我们要完成的是相对映射。‘a'的ASC值是97,因此我们需要将各个字符 - ’a’才是相对位置。再次遍历数组时,将数据 - ‘a’才是在CountA数组的下标。
如果数组遍历完成仍然没有返回,那就返回 - 1.
复杂度分析:
只遍历了两次数组,花费2N,所以是O(N)。