题目描述
来自LeetCode第387题：字符串中的第一个唯一字符
给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
s只包含小写字母。
图片：
分析
整体思路是遍历每一个字符，统计每个字符出现的次数，然后再遍历一遍字符串，找到第一个出现次数为1的字符。
因此我们需要一个数组，用来：统计26个字母出现的次数。
第二次遍历的时候，从左到右查看每个字符是否只出现了一次。
按照这个逻辑，这个题天然地适合用哈希表来做。每个字符的ASCII码值可以作为哈希表的索引，出现的次数作为值。
那么哈希生成函数就是：
1
2
3
|
hash(char c) {
return 'c' - 'a';
}
|
这时候，就可以用一个长度为26的数组来模拟哈希表。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int firstUniqChar(char* s) {
int times[26];
int len = strlen(s);
for (int i=0;i<len;i++){
times[s[i]-'a']++;
}
for(int i=0;i<strlen(s);i++){
if (times[s[i]-'a']==1){
return i;
}
}
return -1;
}
|
问题延申
原题是非常简单的，只要求第一次的索引，所以代码也无需优化，第二次遍历原字符串即可。
但是如果题目变种一下，要求返回所有只出现一次的字符呢？
注意，这里改成了只出现的第一个的字符，而不是它的索引。
新的问题用原来的逻辑也是可行的，但是效率不高。
因为第二次遍历原字符串时，可能会多次查找同一个字符的出现次数。
假设原字符串很大，那么第二次遍历的复杂度与第一次相当。
那么第二次遍历，如何如何防止对一个字符多次查表呢？
因为第一次遍历是从左到右（当然也可以从右到左），第二次遍历也是从左到右，第一次遍历的字母种类，第二次也要查一次。
那么我们可以用一个队列来存储第一次遍历时，出现过的字母。
第二次遍历时，无需遍历原字符串s，而是遍历队列中的字母。
代码实现
无队列版：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int firstUniqChar(char* s) {
int times[26];
int len = strlen(s);
for (int i=0;i<len;i++){
times[s[i]-'a']++;
}
for(int i=0;i<strlen(s);i++){
if (times[s[i]-'a']==1){
return i;
}
}
return -1;
}
|
加入队列版：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
int firstUniqChar(char* s) {
int times[26];
int queue[26];
int last = -1; // 队列尾指针
int len = strlen(s);
for (int i=0;i<len;i++){
times[s[i]-'a']++;
if (times[s[i]-'a']==1){
queue[++last] = s[i]-'a'; // 入队
}
}
for(int i=0;i<=last;i++){
if (times[queue[i]]==1){
return queue[i]+'a'; // 返回字符
}
}
return -1;
}
|
复杂度分析
原题的时间复杂度是O(n)，空间复杂度是O(1)。
延申题的时间复杂度也是O(n)，空间复杂度是O(1)。
不过，延申题使用队列后，第二次遍历的次数变少了。
以后遇到要两次遍历，前后的顺序相同时，为了避免重复，可以考虑用队列。
毕竟，队列是先进先出。