方法1：
看到这个题目，最直观的想法就是就是遍历法，也就是从头开始取字符串中的一个字符，将其与其后的所有字符比较，如果有相同的字符，那么就证明它不是只出现一次的字符。当第一次出现遍历完其后字符并且没有重复时，表明这个字符就是“第一个只出现一次的字符”。如果字符串有n个字符，每个字符可能与后面的O(n)个字符相比较，因此这种思路的时间复杂度是O(n2)。
方法2：
题目中要求第一个只出现一次的字符，那么就跟字符出现的次数有关。我们考虑如何统计字符出现的次数，然后找出第一个次数为1的那个字符。这里我们需要一个数据容器来保存字符出现次数，并且能够通过字符找出其相对应的次数。哈希表就是一种常用用的容器。
我们可以定义哈希表的键值(Key)是字符的ASCII值，而值(Value)是该字符出现的次数。同时我们需要扫描两次字符串，第一次扫描字符串时，每扫描到一个字符就在哈希表的对应项中把次数加1。接下来第二次扫描的时候，没扫描到一个字符就能在哈希表中得到该字符出现的次数。找出第一个Value为1的那个key就是我们需要找到那个字符。
#include "stdafx.h" #include<iostream> #include<stdlib.h> using namespace std; //O(n^n)的时间复杂度 char FirstNotRepeatingChar2(char *pString) { //如果是空指针，返回 if(pString==NULL) return ' '; int len=strlen(pString); for(int i=0;i<len;i++) { int flag=0;//标识位，0表示这个字符只出现一次。 for(int j=i+1;j<len;j++) { if(pString[i]==pString[j]) { flag=1;//1表示在当前字符后面存在于该字符相同的字符。 } } if(flag==0) return pString[i]; } return ' '; } //O(n)的时间复杂度 char FirstNotRepeatingChar(char *pString) { //如果是空指针，返回 if(pString==NULL) return ' '; //定义hash表长度256，并创建哈希表 const int len=256; int hashtable[len]; for(int i=0;i<len;i++) { hashtable[i]=0; } char *pHashkey=pString; //第一遍遍历字符串，求出每个字符出现的次数 while((*pHashkey)!=' ') { hashtable[*(pHashkey++)]++; } pHashkey=pString; //第二遍遍历字符串，求出第一个只出现一次的字符，每次都是按照字符串的顺序遍历 while((*pHashkey)!=' ') { if(hashtable[*pHashkey]==1) return *pHashkey; pHashkey++; } return ' '; } //这里字符要有从小到大排列，如果把下面字符改成“baccdeff”，输出的依然是4 9 b b int main(int argc,char* argv[]) { char *pString="abaccdeff"; //cout<<pString<<endl; //cout<<pString[1]<<endl; cout<<sizeof(pString)<<endl;//4 cout<<strlen(pString)<<endl;//9 cout<<FirstNotRepeatingChar(pString)<<endl; cout<<FirstNotRepeatingChar2(pString)<<endl; cout<<"pos"<<endl; int a; cin>>a; return 0; }
转 http://www.cnblogs.com/xwdreamer/archive/2012/09/26/2703739.html