首页 > 代码库 > careercup-中等难度 17.9
careercup-中等难度 17.9
17.9 设计一个方法,找出任意指定单词在一本书中的出现频率。
解法:
1 单次查询
遍历这本书的每个单词,计算给定单词出现的次数。时间复杂度O(n),我们无法继续优化它,因为书中的每个单次都需要访问一次。当然,如果我们假设书中的单词是均匀分布的,那我们就可以只统计前半本书某个单次出现的次数,然后乘以2;或是只统计前四分之一本书某个单次出现的次数,然后乘以4。
2 多次查询
如果我们要重复执行查询,那么,或许值得我们多花些时间,多花些内存,对全书进行预处理。我们可以构造一个散列表,将单词映射到该单词的出现频率。这么一来,任意单词的频率就可以在O(1)时间内找的,具体事项代码如下:
#include<string>#include<map>#include<iostream>using namespace std;map<string,int> setupDictionary(string book[],int n){ int i; map<string,int> mp; for(i=0;i<n;i++) { mp[book[i]]++; } return mp;}int getFrequency(map<string,int> &mp,string s){ return mp[s];}int main(){ string str[10]={"a","b","a","c","d","d","e","f","e","e"}; map<string,int> mp=setupDictionary(str,10); cout<<getFrequency(mp,"a")<<endl;}
careercup-中等难度 17.9
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。