剑指OFFER之第一个只出现一次的字符（九度OJ1283）
剑指OFFER之第一个只出现一次的字符（九度OJ1283）
用户1154259
发布于 2018-01-17 19:25:25
发布于 2018-01-17 19:25:25
题目描述：
在一个字符串(1<=字符串长度<=10000，全部由大写字母组成)中找到第一个只出现一次的字符。
输入：
输入有多组数据 每一组输入一个字符串。
输出：
输出第一个只出现一次的字符下标，没有只出现一次的字符则输出-1。
样例输入：
ABACCDEFF
AA样例输出：
1
-1解题思路：
首先考虑到时间复杂度，对字符串进行排序或者双层扫描都会到达O(nlong)---O(n^2)的地步。
所以我们考虑额外使用一个数组进行计数，线性时间扫描数组，然后再按照原来的顺序扫描数组找到次数为1的，进行输出。
for(i=0;i<length;i++){
cnt[c[i]-'A']++;
}
for(i=0;i<length;i++){
if(cnt[c[i]-'A'] == 1){
num = i;
break;
}
}全部代码
#include <stdio.h>
#include <string.h>
int main(){
int i;
char c[10000];
int cnt[24];
while(scanf("%s",&c)!=EOF){
memset(&cnt,0,sizeof(int)*24);
int num = -1;
int length = strlen(c);
for(i=0;i<length;i++){
cnt[c[i]-'A']++;
}
for(i=0;i<length;i++){
if(cnt[c[i]-'A'] == 1){
num = i;
break;
}
}
printf("%d\n",num);
}
return 0;
}
/**************************************************************
Problem: 1283
User: xhalo
Language: C
Result: Accepted
Time:20 ms
Memory:912 kb
****************************************************************/本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014-06-20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录