第一个只出现一次的字符

题目:在字符串中找出第一个只出现一次的字符。如输入“absccdeff”,则输出b.

由于题目与字符出现的次数有关,我们需要统计每个字符出现的次数,要达到这个目的,我们需要一个数据容器来存放每个字符的出现次数,在这个数据容器中可以根据字符来查找它出现的赐福,也就是说这个容器的作用是把一个字符映射成一个数字。由此我们可以想到用哈希表。

同时,我们还需要从头开始扫描字符串两。第一次扫描字符串时,每扫描到一个字符就在哈希表的对应项中把次数加一。第二次扫描时,每扫描到一个字符就能从哈希表中得到该字符出现的次数,这样第一个只出现一次的字符就是符合要求的输出。

char FirstNotRepeatChar(char* pString)
{
    if (pString == NULL)
    {
        return '\0';
    }
    const int tableSize = 256;
    unsigned int hashtable[tableSize];
    for (unsigned int i = 0; i < tableSize; ++i)
    {
        hashtable[i] = 0;
    }
    char* pHashKey = pString;
    while (*(pHashKey) != '\0')
    {
        hashtable[*(pHashKey++)]++;
    }
    pHashKey = pString;
    while (*pHashKey != '\0')
    {
        if (hashtable[*pHashKey] == 1)
        {
            return *pHashKey;
        }
        *pHashKey++;
    }
    return '\0';
}

int main()
{
    char* str = "abaccdeff";
    char ret = FirstNotRepeatChar(str);
    cout << ret << endl;
    system("pause");
    return 0;
}
相关文章
相关标签/搜索