题目:有一个江洋大盗,他每次写信都是从一张报纸上剪下单词,再把单词贴在信上。假如某张报纸的单词保存在vector<string>paper 中,而信的单词保存在vector<string>letter 中,写一个算法程序判别该报纸可不可以生成该信?
对比一些方法: 这里假设paper:(m个单词,每个单词平均d个字母),letter:(n个单词,每个单词平均d个字母)。对于中文词语而言,一般2~4个字左右,对于英文单词,d就要大一点,但基本上也是常数。因此d远远小于m,下面比较的时候就不考虑单词中每个字符间的比较了。
(1) 蛮力匹配:
把n中每个单词与m中的每个单词一一比较。时间复杂度为:O(m*n)。估计谁也不会选这种。
(2) 二分查找:要求,对paper建有序索引。
paper排序的时间复杂度最好为O(m*logm)。
对letter中的所有单词二分查找的时间复杂度为O(n*logm)
总的时间复杂度为O((m+n)*logm). 比蛮力查找效率要好不少。
缺点:如果换了新报纸,所有的单词都必须重新排序,需要O(m*logm)的时间来建立索引。
(3) trie树: 要求,对paper建trie索引树
paper建立trie树的时间复杂度为O(m)。
对letter中所有单词在trie树中查找的时间复杂度为O(n).
总的时间复杂度为O(m+n)。效率绝对要比二分查找好。
优势: 如果换了新报纸,重新建立一颗trie树的时间O(m)也小于二分查找建立有序索引的时间O(m*logm)要小的多。
缺点:建立trie树所需要的空间代价是很大的。如果是中文词语的trie树,那么放进全部加载进内存是很可怕的,需要把trie树用B树的方法存储在磁盘上。详见:《Trie树
》
(4) Hash表: 要求,对paper建立Hash结构
建立Hash表结构的时间复杂度为O(m),注意需要计算每个单词的HashCode的时候,很可能要遍历单词中的每个字母。
对letter中所有单词在Hash结构中查找的时间复杂度为O(n)。当然,这是在没有任何散列冲突的理想情况下。选择好HashCode的计算方式和散列表的大小,可以将冲突降到很低。因此我们这里不考虑冲突。
总的时间复杂度为O(m+n)。由此可见,Hash表结构与Trie树的效率都是相当的客观。
缺点:如果换报纸。为了考虑冲突的可能性,Hash结构的大小可能需要重新考虑。这一点很麻烦。当然,存储空间上应该会比Trie要好一些,但实际应用上并不比Trie方便。
(5) 归并查找:要求,对letter和paper都建立有序索引。
对letter和paper排序的时间复杂度分别为O(m*logm)和O(n*logn)
归并查找的时间复杂度为O(m+n)
总的时间复杂度为O(m*logm+n*logn+m+n)
总结:对于这几种方法而言,我更加青睐于trie树。因为我相信报纸中的单词数量基本上是保持稳定的,不可能达到海量级别。Trie树的空间代价其实并不算什么。
分享到:
相关推荐
小Q最近遇到了一个难题:把一个字符串的大写字母放到字符串的后面,各个字符的相对位置不变,且不能申请额外的空间。 你能帮帮小Q吗? 输入描述: 输入数据有多组,每组包含一个字符串s,且保证:1 输出描述: 对于每...
腾讯在线笔试题-把字符串“I am from china.”反转成为“I am from china.”,以及把整个字符串逆序。
腾讯开源的以提升问题定位效率为初衷,提供染色抓包、全息日志和异常发现的Node.js框架。.zip,腾讯服务器网
腾讯通常见问题
asp.net的各种常用正则表达式,匹配特定字符串,匹配特定数字,匹配ip地址,匹配身份证,匹配腾讯QQ号,匹配首尾空白字符,匹配空白行,匹配双字节字符,匹配中文字符等等
腾讯编程马拉松考试题目-马虎的龙哥、照片评级、图形匹配
Delphi url 编码及转码及特殊字符串替换--百度和腾讯用的就是这个.mht
腾讯公司发展战略与前景.pdf
腾讯面试经验,腾讯面经,腾讯面试经验,腾讯面经,腾讯面试经验,腾讯面经
腾讯产品经理素质与技能要求.pdf 腾讯公司基层管理干部职业领导力发展规划书.pdf 腾讯公司职业发展体系(141页) (1).pdf 腾讯公司职业发展体系介绍-专业职级.pptx 腾讯领导力职业发展通道标准.pdf 腾讯员工职业发展...
AI与机器人的42个大问题-腾讯AI lab,AI与机器人的42个大问题-腾讯AI lab
腾讯大规模知识图谱的构建与在自然语言理解中的应用腾讯大规模知识图谱的构建与在自然语言理解中的应用腾讯大规模知识图谱的构建与在自然语言理解中的应用腾讯大规模知识图谱的构建与在自然语言理解中的应用腾讯大...
腾讯业务产品线众多,拥有海量的活跃用户,每天线上产生的数据超乎想象,必然会成为数据大户,为了保证公司各业务产品能够使用更丰富优质的数据服务,腾讯的大数据平台做了那些工作?具备哪些能力?大数据,这个词...
腾讯 QMUI Team 常用的 Xcode Code Snippets 代码片段,加速开发效率!.zip,用于Xcode使用的iOS通用代码片段,其中也包含若干专用于QMUI iOS框架的代码片段。
面对多样且复杂的场景,比如开会环境嘈杂、同一地点多设备接入、房间声学参数不理想等,腾讯会议如何通过对音频信号的处理持续保障高品质通话,提升沟通效率?本文是腾讯多媒体实验室音频技术专家李岳鹏在「腾讯技术...
微信小程序 影音娱乐 仿腾讯视频小程序 (源代码+截图)微信小程序 影音娱乐 仿腾讯视频小程序 (源代码+截图)微信小程序 影音娱乐 仿腾讯视频小程序 (源代码+截图)微信小程序 影音娱乐 仿腾讯视频小程序 (源...
腾讯外传|马化腾的腾讯帝国
腾讯:2021腾讯智慧零售T+品牌私域价值榜.pdf 腾讯:2021腾讯智慧零售T+品牌私域价值榜.pdf 腾讯:2021腾讯智慧零售T+品牌私域价值榜.pdf 腾讯:2021腾讯智慧零售T+品牌私域价值榜.pdf 腾讯:2021腾讯智慧零售T+品牌...
腾讯会议pc版备份 腾讯会议pc版备份