面试题35：第一个只出现一次的数字

话说写博客真是个累人的干活，即使是我写如此简单，篇幅如此短小的博客，有时候也真想一弃了之，放任不管。恰逢这几天忙着考试，今天一门，明天一门，后天还有一门。一学期了没好好学，现在可真是后悔呀。。。忙得头晕转向，甚至复习时间都感觉很不够用。但我电脑上设置了闹钟，每天道时间就会提醒我该写博客了。今天打开一看，咦？很久没遇到如此简单的题目了，赶紧写吧，多出来的时间写这一段废话，没什么用处，发发牢骚而已。诸君看看就好，:)

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

分析

此题我觉得是简单哈希表使用的范例。哈希表是啥？就是将一个给定的数据映射到一个确定的位置上。在此题中，”给定的数据”就是该字符串中的每一个字符，因为C语言的编码是一ASCII为基础的，而ASCII只有128个字符，除过33个不可见字符的话就更少了。所以为了稳妥起见，我们定义一个长度为256的整形数组，全部初始化为0.数组的下标表示字符串中某一个字符的ASCII码，而值代表该字符出现的次数。然后我们遍历一次该字符串，每遇到一个字符，就对其对应的位置加1.完成之后就能统计出该字符串中都有哪些字符，各出现了多少次。然后再遍历一遍字符串，若某字符对应的位置上的值为1，它就是我们要找的字符了，return退出即可。

如果使用蛮力法，每遇到一个字符，就在后面看它有没有再次出现。直到找到第一个只出现一次的字符。这种方法的时间复杂度为O(n²),显然没第一种方法高效，代码从略。

第一个方法代码如下：

char FirstNotRepeatingChar(const string&amp; str) { vector<int> count; count.resize(256); int i; for(i=0;i<256;++i) { count[i]=0; } for(i=0;i<str.size();++i) { count[str[i]]++; } for(i=0;i<str.size();++i) { if(count[str[i]]==1) return str[i]; } throw new exception(); }

以上

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往