题目描述
题目链接:387. First Unique Character in a String
Given a string, find the first non-repeating character in it and return its index. If it doesn’t exist, return -1.
例子
例子 1
Input: “leetcode” Output: 0
例子 2
Input: “loveleetcode” Output: 2
Note
You may assume the string contains only lowercase English letters.
解题思路
题目涉及统计字母出现个数,很自然想到一次遍历通过哈希表统计字母出现个数(这里由于题目指明字符串只包含小写字母,所以可以用 std::vector
作为哈希表),第二次遍历找出第一个出现次数为 1 的字符返回下标,否则返回 -1,代码如下:
#include <vector>
#include <string>
class Solution {
public:
int firstUniqChar(std::string s) {
std::vector<int> count(26, 0);
for (char letter: s) {
count[letter - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
if (count[s[i] - 'a'] == 1) return i;
}
return -1;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1) 需要的哈希表空间是固定的所以可以理解为常数空间