@linux1s1s
2015-05-05T21:07:13.000000Z
字数 781
阅读 1808
C/C++
题目:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。 分析:这道题是2006年google的一道笔试题。
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int i = 0;
char* str = "abaccdeff";
int ch[256];
memset(ch,0,sizeof(ch));
int len = strlen(str);
//用来存放字符串某个字符出现的最后位置(从0开始)
int chset[256];
memset(chset,0,sizeof(chset));
//把字符转化为USCII码,然后作为数组下标,如果出现多次,该下标数组值会累加,如果出现一次,那么就是1
for(i=0; i<len; i++)
{
ch[str[i]-'0']++; //位图初始化全为0
chset[str[i]-'0'] = i;
}
//添加哨兵 min
int min = chset[str[0]-'0'];
int k = 0;
//遍历寻找数组ch值为1,并且出现的位置在chset数组中最小的字符
for(i=0; i<len; i++)
{
if(ch[str[i]-'0'] == 1)
{
if(chset[str[i]-'0'] < min)
{
min = chset[str[i]-'0'];
k = i;
}
}
}
printf("in str:%s\nfirst apprear once is %c\n",str,str[k]);
system("PAUSE");
return 0;
}
之前有篇博客http://blog.chinaunix.net/uid-9950859-id-98760.html?page=2
给出的解决思路有个问题,字符串必须是顺序的,否则会出现bug,这里给出的算法,可以无视顺序这个问题。