题目描述
给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。
示例:
s = "leetcode"
返回 0
s = "loveleetcode"
返回 2
提示:你可以假定该字符串只包含小写字母。
算法1
哈希
先记录每个字母出现的次数 然后找出第一个为出现1次的字母索引
C++ 代码
class Solution {
public:
map<char, int> mm;
int firstUniqChar(string s) {
for (int i = 0; i < s.size(); i++) {
mm[s[i]]++;
}
//遍历字符串 查找哈希中出现的次数
for (int i = 0; i < s.size(); i++) {
if (mm[s[i]] == 1) return i;
}
return -1;
}
};
算法2
算法1的改进 使用了unordered_map 而不是 map 查找更快
C++ 代码
class Solution {
public:
unordered_map<char, int> mm;
int firstUniqChar(string s) {
for (int i = 0; i < s.size(); i++) {
mm[s[i]]++;
}
//遍历字符串 查找哈希中出现的次数
for (int i = 0; i < s.size(); i++) {
if (mm[s[i]] == 1) return i;
}
return -1;
}
};
算法3
直接使用 int arr[26]的数组作为字母的哈希表
字母与’a’的差值作为数组索引速度更快
C++ 代码
class Solution {
public:
int mm[26] = { 0 };
int firstUniqChar(string s) {
for (int i = 0; i < s.size(); i++) {
int idx = s[i] - 'a';
mm[idx]++;
}
//遍历字符串 查找哈希中出现的次数
for (int i = 0; i < s.size(); i++) {
int idx = s[i] - 'a';
if (mm[idx] == 1) return i;
}
return -1;
}
};
再附赠一个搞笑(不是高效)的瞎优化翻车代码
加了vector的代码 反而不如数组直接简单高效
class Solution {
public:
vector<int> mm[26];
int firstUniqChar(string s) {
for (int i = 0; i < s.size(); i++) {
int idx = s[i] - 'a';
mm[idx].push_back(i);
}
//遍历哈希表 找到第一个只记录了一个的索引值的哈希元素
int ret = 999999;
for (int i = 0; i < 26; i++) {
if (mm[i].size() == 1 && mm[i][0] < ret) { ret = mm[i][0]; }
}
return ret == 999999 ? -1 : ret;
}
};