具体思路比较简单，首先声明一个长度为 128（容纳 char 类型）的 int 数组，数组中数字如果是-1，说明还没找到，如果是-2，说明出现已经超过一次，如果大于 0，则标识找到的位置。所以只要循环输入字符串一遍，再循环 freq 数组两遍(第一遍初始化,第二遍寻找第一个只出现一次的元素)即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int FirstNotRepeatingChar(string str) {
if(str.size()==0) return -1;
int freqArray[128];
for(int i=0;i<128;i++) freqArray[i]=-1;
for(int i=0;i<str.size();i++){
int pos=(int)(str[i]);
if(freqArray[pos]==-2) continue;
else if(freqArray[pos]==-1) freqArray[pos]=i;
else if(freqArray[pos]>=0) freqArray[pos]=-2;
}
int firstPos=str.size();
for(int i=0;i<128;i++){
int pos=freqArray[i];
if(pos<0) continue;
if(pos<firstPos) firstPos=pos;
}
if(firstPos==str.size()) return -1;
else return firstPos;
}
};
|