（剑指Offer）面试题35：第一个只出现一次的字符

题目：

在字符串中找出第一个只出现1次的字符，如输入“abaccdeff”，则输出b。

思路：

1、暴力遍历

从头开始扫描字符串中的每个字符，当访问某个字符时，取该字符与后面的每个字符相比较，如果没有重复的字符，那么该字符就是第一个只出现一次的字符。

时间复杂度：O(n^2)

2、Hash

通过hash表来记录字符串中每个字符出现的次数，hash表可以通过一个长度为256的数组来实现，因为字符是一个长度为8的数据类型，总共有256种可能。

（注意：char数据类型的表示范围为-128-127，unsigned char数据类型的表示范围为0-255，需明确字符串中的字符属于哪个范围，这里只考虑大于0的）

第一遍扫描字符串，每扫描一个字符就在hash表中相应位置上+1，记录下每个字符出现的次数；

第二遍扫描字符串，每扫描一个字符就从hash表中得到该字符出现的次数，如果为1，则该字符为第一个只出现一次的字符。

代码：

#include <iostream>

using namespace std;

char firstNotRepeatingChar(char* pString){

    if(pString==NULL)

        return '\0';

    const int tableSize=256;

    unsigned int hashTable[tableSize];

    for(int i=0;i<tableSize;i++)

        hashTable[i]=0;

    char* pHashKey=pString;

    while(*pHashKey!='\0'){

        hashTable[*pHashKey-'0']++;

        pHashKey++;

    }

    pHashKey=pString;

    while(*pHashKey!='\0'){

        if(hashTable[*pHashKey-'0']==1)

            return *pHashKey;

        pHashKey++;

    }

    return '\0';

}

int main()

{

    char str[]="abacbd";

    cout << firstNotRepeatingChar(str) << endl;

    return 0;

}

在线测试OJ：

http://www.nowcoder.com/books/coding-interviews/1c82e8cf713b4bbeb2a5b31cf5b0417c?rp=2

在一个字符串(1<=字符串长度<=10000，全部由大写字母组成)中找到第一个只出现一次的字符。

AC代码：

class Solution {

public:

    int FirstNotRepeatingChar(string str) {

        if(str.size()<=0)

            return -1;

        const int tableSize=26;

        int hashTable[tableSize];

        for(int i=0;i<tableSize;i++)

            hashTable[i]=0;

        for(unsigned int i=0;i<str.size();i++)

            hashTable[str[i]-'A']++;

        for(unsigned int i=0;i<str.size();i++){

            if(hashTable[str[i]-'A']==1)

                return i;

        }

        return -1;

    }

};

class Solution {

public:

    int FirstNotRepeatingChar(string str) {

        if(str.size()<=0)

            return -1;

        const int tableSize=256;

        int hashTable[tableSize];

        for(int i=0;i<tableSize;i++)

            hashTable[i]=0;

        for(unsigned int i=0;i<str.size();i++)

            hashTable[str[i]]++;

        for(unsigned int i=0;i<str.size();i++){

            if(hashTable[str[i]]==1)

                return i;

        }

        return -1;

    }

};

巴特西

（剑指Offer）面试题35：第一个只出现一次的字符

题目：

思路：

代码：

在线测试OJ：

最新文章

热门文章