当前位置: 首页 > 面试 > 正文

给定一个字符串数组,从中找出第一个只出现一次的字母

关键字:
1 星2 星3 星4 星5 星 (2 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

今天针对该问题看有什么可以优化的地方: 首先看看网上一个同学的解法:

利用哈希表,因为字符最多只有255个,可以 利用这个特性建立一个哈希表,将字符串中所有的字符映射到 这个哈希表中,记录出现的每个字符的个数。最后查找哈希表 获取第一个出现字数为一的字母。   这里有一个问题,我们如何知道我们取到的是字符串中的第一 个出现一次的字母,这里要求我们在映射字符的时候,顺便将其 第一次出现的位置记录到哈希表结构中去。位置最靠前的当然就 是第一个只出现一次的字母了。   在实现过程中,可以自己实现一个定制的哈希表结构,但是 我嫌太麻烦了,就利用了一些个小技巧,利用一个Set来记录 出现了那些字符,在定义一个结构体记录每个字符出现的次数和 首次在字符串中出现的位置。

改进算法1

如果对bitmap熟悉的话,首先应该考虑就是bitmap,可以简单快速的实现该算法。首先由一个256位的int数组用作bitmap。这256个位置将用于表示一个字符的ASCII码值。例如位置97表示字符a。bitmap的妙处就在于能利用数组的地址值信息。如果‘a’出现一次我们就在int[97]中增加1。这样数组a[256]中值的大于就表示该位置对应的字符出现过几次。a[int(b[i])]+=1 就是对字符出现的个数计数。第二个循环就是遍历‘dcbbdcsk’。找到第一个a[int(b[i])]==1的字符。那么这个字符即为所求。

改进2

对上面的bitmap是否还有可改进的呢? 答案是yes。 题目中要求的只是字母。所以根本不需要256个int来计数,这里只需要考虑a-zA-Z 52个字母,a-z ASCII为97-122. A-Z 为65-90. 由于大小写字母ASCII不连续。为了处理方便我们可以用一个58(122-65+1)长的数组。对应的a[int(b[i])]只需要改为a[int(b[i])-65]. 空间复杂度就由原来o(256)降到o(58)。时间复杂度不变。如果只是用52长的数组也可以,那需要分别考虑大小写,会增加时间代价。

改进3

那能再抠点空间出来吗?试试吧。我们再来看看题目要求。除了有字母的限制外。还有‘第一个只出现一次’。也就是所有字符只有3种可能

没有出现 =0
出现1次 =1
出现多于1次 >1
只有3种状态是否需要用int来表示呢?当然不用。我们知道对于那种状态只需要log(n)bit就可以解决。所以这里不需要58个int,只需要58个“2bit”,即15个byte的数组。这样就需要用逻辑操作。 这里令x=int(b[i])-65 Byte a[15]以初始化为0 a[int(b[i])]+=1 改为

1
2
3
4
5
if(((a[x/4+1] & ox10000000 >>((x%4−1)x2)) == 0)
 
a[x/4+1]+=ox10000000 >>((x%4)x2−1)  
 
a[int(b[i])]==1改为 ((a[x/4+1] & ox10000000 >>((x%4−1)x2)) == 1

这样空间复杂度将再度降低。 总结,做题之前一定要看清题目要求。

本文固定链接: http://www.chepoo.com/the-first-one-to-find-out-the-letters-appear-only-once-from-strings.html | IT技术精华网

给定一个字符串数组,从中找出第一个只出现一次的字母:等您坐沙发呢!

发表评论