题目：

在字符串中找出第一个只出现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 
     
      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
     

在线测试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

 

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