careercup-中等难度 17.9-白红宇

careercup-中等难度 17.9

阅读量：4883 次

发布时间：2019-06-11

本文共 719 字，大约阅读时间需要 2 分钟。

17.9 设计一个方法，找出任意指定单词在一本书中的出现频率。

解法：

1 单次查询

遍历这本书的每个单词，计算给定单词出现的次数。时间复杂度O(n)，我们无法继续优化它，因为书中的每个单次都需要访问一次。当然，如果我们假设书中的单词是均匀分布的，那我们就可以只统计前半本书某个单次出现的次数，然后乘以2；或是只统计前四分之一本书某个单次出现的次数，然后乘以4。

2 多次查询

如果我们要重复执行查询，那么，或许值得我们多花些时间，多花些内存，对全书进行预处理。我们可以构造一个散列表，将单词映射到该单词的出现频率。这么一来，任意单词的频率就可以在O(1)时间内找的，具体事项代码如下：

#include
     
      #include
      #include
       
        using namespace std;map
        
          setupDictionary(string book[],int n){    int i;    map
         
           mp;    for(i=0;i
          
            &mp,string s){ return mp[s];}int main(){ string str[10]={ "a","b","a","c","d","d","e","f","e","e"}; map
           
             mp=setupDictionary(str,10); cout<
            
             <

转载于:https://www.cnblogs.com/wuchanming/p/4161020.html

你可能感兴趣的文章