首页 > 代码库 > 剑指OFFER之第一个只出现一次的字符（九度OJ1283）
剑指OFFER之第一个只出现一次的字符（九度OJ1283）
题目描述：
在一个字符串(1<=字符串长度<=10000，全部由大写字母组成)中找到第一个只出现一次的字符。
- 输入：
输入有多组数据
每一组输入一个字符串。
- 输出：
输出第一个只出现一次的字符下标，没有只出现一次的字符则输出-1。
- 样例输入：
ABACCDEFFAA
- 样例输出：
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****************************************************************/
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。