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

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


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


分析

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

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

第一个方法代码如下:

FirstNotRepeatingChar(const string& str)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
{
vector&lt;int&gt; count;
count.resize(256);
int i;
for(i=0;i&lt;256;++i)
{
count[i]=0;
}
for(i=0;i&lt;str.size();++i)
{
count[str[i]]++;
}
for(i=0;i&lt;str.size();++i)
{
if(count[str[i]]==1)
return str[i];
}
throw new exception();
}

以上

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

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

<div>来自为知笔记(Wiz)</div>