第一个只出现一次的字符

题目：在字符串中找到第一个只出现一次的字符。如输入“abaccdeff”，则输出‘b’。

分析：最直观解法，从头扫描这个字符串中的每个字符。当访问到某个字符时拿这个字符和后面的每个字符比较，如果在后面没有发现重复字符，则该字符就是只出现一次的字符。这种方法的时间复杂度为O(n2)。当然我们应该有更快的方法：利用哈希表的key和value，key是字符，value是次数。这样就只需要扫描字符串两次就可以。这里我们用每个字母的ASCII码值作为数组下标对应数组的一个数字，而数组中存储的是每个字符出现的次数。实现如下：

char FirstNotRepeatingChar(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‘;
    
}

本文出自 “仙路千叠惊尘梦” 博客，请务必保留此出处http://secondscript.blog.51cto.com/9370042/1586674

第一个只出现一次的字符

原文：http://secondscript.blog.51cto.com/9370042/1586674