Question

C/C++编程题:查找字符串中第一个只出现一次的字符，例如字符串为“abaccde”,则输出b,两种算法实现

Answer 1

用哈希的方式，把字符在哈希表中统计出每一个的个数来，然后从小开始遍历出第一个为1的
代码如下：
#include <stdio.h>
#include <string.h>

char get_onlyone(char* str)
{
char i;
int hash[128];
memset(hash, 0, sizeof(hash));
for(i = 0; str[i]; i++) {
hash[str[i]]++;
}
for(i = 0; i < 128; i++) {
if(hash[i] == 1) break;
}
return i;
}

int main(void)
{
char str[128];
while(scanf("%s", str) != EOF) {
printf("%c\n", get_onlyone(str));
}
return 0;
}

追问

这样写有问题啊，如果字符串为“aadbc”,应该输出d,但按你的程序输出为b

Answer 2

第一种用普通的数组记录某个字母出现的次数，遍历完字符串就知道哪个出现一次。
第二种可以用哈希思想，去判断某个字母是否出现多次，复杂度也是便利一边的时间

追问

能具体写一下代码么？或者伪代码也行，谢了啊

追答

第一种：
int i,a[26]={0}
for(i=0;i<strlen(str);i++)
a[str[i]-'a')]++;
for( i=0;i<strlen(str);i++)
if(a[i]==1)
printf("%c\n");

第二种：(这个不是标准的哈希）
int a[26];
void simpleHash(char x){
int location = (x-'a')%26;
a[location]++;
}
for(i=0;i<strlen(str);i++)
simpleHash(str[i]);
for( i=0;i<strlen(str);i++)
if(a[i]==1)
printf("%c\n");