给定一个字符串 s ,找到 它的第一个不重复的字符,并返回它的索引 。如果不存在,则返回 -1 。
示例 1:
输入: s = "leetcode"
输出: 0
示例 2:
输入: s = "loveleetcode"
输出: 2
示例 3:
输入: s = "aabb"
输出: -1
提示:
1 <= s.length <= 105
s 只包含小写字母
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/first-unique-character-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
方法一:O(2N)时间复杂度解法
思路:
- 使用hash表记录字符出现的次数
- 再次遍历输入字符串,判断该字符在hash表中出现的次数
该解法时间复杂度为O(2*N)
代码如下:
class Solution {
public:
int firstUniqChar(string s) {
// 使用hash表,时间复杂度2*N(可以使用map也可以使用数组进行映射)
map<char, int> hash;
for (size_t i = 0; i < s.length(); i++)
{
hash[s.at(i)]++;
}
for (size_t i = 0; i < s.length(); i++)
{
if (hash[s.at(i)] == 1)
{
return i;
}
}
return -1;
}
int firstUniqChar2(string s) {
// 使用hash表,时间复杂度2*N(可以使用map也可以使用数组进行映射)
int arr[26] = { 0 };
for (size_t i = 0; i < s.length(); i++)
{
arr[s.at(i) - 'a']++;
}
for (size_t i = 0; i < s.length(); i++)
{
if (arr[s.at(i) - 'a'] == 1)
{
return i;
}
}
return -1;
}
};
方法二:O(N)时间复杂度解法
- 使用hash表记录字符出现的索引位置,初始化为-1。
- 如果是第一次出现记录索引位置
- 如果不是第一次出现,设置为-2
- 对hash表根据索引进行排序,找到第一个非负数
- memset是将内存中的每一个byte都设置为对应的value,所以不能用memset设置
- 要用int或者long来表示table,因为里面存的是索引~~
int firstUniqChar(string s) {
long table[26];
//memset(table,-1,sizeof(table)/sizeof(long));
for (int i = 0;i < 26;++i)
{
table[i] = -1;
}
for (int i = 0; i < s.size();++i)
{
int index = s[i] - 'a';
if (table[index] == -2)
{
continue;
}
if (table[index] != -1)
{
table[index] = -2;
continue;
}
table[index] = i;
}
sort(table,table+26);
for(int i = 0;i < 26;++i)
{
if (table[i] == -1 || table[i] == -2)
{
continue;
}
return table[i];
}
return -1;
}