题目链接
题意
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
解题思路
可以用stl Map 也可以自己用数组实现简单的hashMap。key为字符唯一对应的一个idx，value为字符第一次出现的位置。初始化为-1，若第二次出现则标记为-2。
最终遍历hashMap找到最小的>0的value即可。
查询效率为O(1),遍历为O(n),总时间复杂度O(n).
代码
class Solution {
public:
int FirstNotRepeatingChar(string str) {
if(!str.size()){
return -1;
}
//0 to 25 'a' to 'z',26 to 51 'A' to 'Z'
int occurPos[52];
memset(occurPos,-1,sizeof(occurPos));
for(int i=0;i<str.size();++i){
int idx;
if(str[i]>='a'&&str[i]<='z'){
idx=str[i]-'a';
}
else{
idx=str[i]-'A'+26;
}
if(occurPos[idx]==-1){
occurPos[idx]=i;
}
else if(occurPos[idx]>=0){
occurPos[idx]=-2;
}
}
int firstPos=53;
for(int i=0;i<52;++i){
if(occurPos[i]>=0&&occurPos[i]<firstPos){
firstPos=occurPos[i];
}
}
if(firstPos==53){
return -1;
}
else{
return firstPos;
}
}
};