Leetcode387. First Unique Character in a String

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

1
2
3
4
5
s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

思路

  • 为每个出现的字符进行计数,并保存他的索引。这些字符是唯一的,所以不能用multimap。

  • 构建一个无序容器,hashtable. unoredered_map。形式:char|(times,index).其中key是字符,value是pair(次数,index)

  • 从头到尾遍历字符串,将每个字符对应的value都更新(次数|index)

Code in C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char,pair<int,int>> m;//key:char:字符。value:int;次数,int:index
int index =s.size();
for(int i=0;i<s.size();i++)
{
m[s[i]].first++;//value.first:出现次数++
m[s[i]].second=i;//value.sencon:字符出现的索引更新为最新
}

for(auto const &it : m)
{
if(it.second.first==1)//这里不能忘记写second啊,只有second才说明是value!
{
index=min(index,it.second.second);//这里一定要写min(index,curindex),否则会返回最后一次的index,而不是第一次出现的!!
}
}
return index==s.size()?-1:index;
}
};

细节

  1. int index =s.size();定义一个全局变量,最后判断index有没有变化,没有变化说明没有唯一字符,返回-1.
  2. if(it.second.first==1)//这里不能忘记写second啊,只有second才说明是value!
  3. index=min(index,it.second.second);//这里一定要写min(index,curindex),否则会返回最后一次的index,而不是第一次出现的!!

总结

  • 看到字符串计数问题就要想到hash table,用空间换时间,很快查找O(1)。因为统计次数,所以key不能重复,也就是不能用multimap,所以用unordered_map!!

  • 注意是无序!!不要用map,他是rbt实现的,构建树的时候就已经排好了序,计数类的题目是不需要排序的,很浪费时间!!O(logn)。

Thanks for Support.