0%

[Leetcode]387. First Unique Character in a String(C++)

题目描述

题目链接: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,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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) 需要的哈希表空间是固定的所以可以理解为常数空间