剑指Offer - 九度1283 - 第一个只出现一次的字符
2013-11-21 21:13
- 题目描述：
-
在一个字符串(1<=字符串长度<=10000，全部由大写字母组成)中找到第一个只出现一次的字符。
- 输入：
-
输入有多组数据
每一组输入一个字符串。
- 输出：
-
输出第一个只出现一次的字符下标，没有只出现一次的字符则输出-1。
- 样例输入：
-
ABACCDEFF
AA
- 样例输出：
-
1
-1
题意分析：
题目要求给定一个大写字母的字符串，找出第一个只出现了一次的字符的下标，从0开始。
由于ascii字符不过128个，用长度为256的数组就能记录下每个字符第一次出现的下标。另外定义EMPTY表示字符未出现过，DUPLICATED表示字符已经重复出现了。
对于每一个字符，
若计数为EMPTY，则记录当前下标。
若记录为正数，表示此字符出现了一次，置为DUPLICATED。
若为DUPLICATED，说明已经重复过了，不用再改。
扫一遍整个字符串和统计数组，时间复杂度strlen(str) + 256，数组空间复杂度256。选出最小的下标值即为不重复的第一个字符。
// 652691 zhuli19901106 1283 Accepted 点击此处查看所有case的执行结果 1020KB 771B 10MS
//
#include <cstdio>
using namespace std; int main()
{
const int MAXN = ;
int i;
char s[MAXN];
int c[];
int min_index;
const int EMPTY = -;
const int DUPLICATED = -; while(scanf("%s", s) == ){
i = ;
for(i = ; i < ; ++i){
c[i] = EMPTY;
}
i = ;
while(s[i] != '\0'){
if(c[s[i]] == EMPTY){
c[s[i]] = i;
}else{
c[s[i]] = DUPLICATED;
}
++i;
}
min_index = EMPTY;
for(i = ; i < ; ++i){
if(c[i] > ){
if(min_index == EMPTY){
min_index = c[i];
}else{
min_index = c[i] < min_index ? c[i] : min_index;
}
}
}
printf("%d\n", min_index);
} return ;
}