题目:在字符串中找出第一个只出现一次的字符。如输入 “abaccdeff”,则输出b。
思路分析:
(1)由于题目与字符出现的次数相关,那么是不是可以统计每个字符在该字符串中出现的次数?要达到这个目的,我们需要一个数据容器来存放每个字符出现的次数。在这个容器中可以根据字符来查找它出现的次数,也就是说这个容器的作用是把一个字符映射成一个数字。在常用的数据容器中,哈希表正是这个用途。
(2)我们可以定义哈希表的键值( key)是字符,而值(Value)是该字符出现的次数。同时我们还需要从头开始扫描字符串两次。第一次扫描字符串时,每扫描到一个字符就在哈希表的对应项中把次数加1。接下来第二次扫描时,每扫描到一个字符就能从哈希表中得到该字符出现的此时。这样第一个只出现一次的字符就是符合要求的输出。
(3)由于本题的特殊性,我们只需要一个非常简单的哈希表就能满足要求。字符(char)是一个长度为8的数据类型,因此总共有256种可能。于是我么创建一个长度为256的数组,每个字母根据其 ASCII 码值作为数组的下标对应数组的一个数字,而数组中存储的是每个字符出现的次数。这样我们就创建了一个大小为256,以字符 ASCII 码为键值的哈希表。
(4)注意点:因为C/C++中的char有三种类型:char、signed char、unsigned char。char类型的符号是由编译器指定的,一般是有符号的,在对字符进行hash时,应该先将字符转为无符号类型;否则当下标为负值时,就会出现越界访问。

具体实现如下:

#include <iostream>
using namespace std;

char FirstNotRepeatingChar(char *s)
{
    if (s == NULL)
        return '\0';

    const int size = 256;
    unsigned int count[size]; // 可用 unsigned int count[size] = {0}; 将数组中每一个元素都初始化为0。
    for (int i = 0; i < size; i++) // 可能上述方法,不一定对所有编译器都适用,所以采用循环的方式更稳妥。
        count[i] = 0;

    char *pKey = s;
    while (*pKey != '\0')
        count[(unsigned char)*(pKey++)]++;

    pKey = s;
    while (*pKey != '\0')
    {
        if (count[(unsigned char)*pKey] == 1)
            return *pKey;

        pKey++;
    }

    return '\0';
}

int main(int argc, const char * argv[]) {

    char str[] = "abaccdeff";

    printf("%c\n", FirstNotRepeatingChar(str));

    return 0;
}
Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐