题目描述
设计一个方法，找出任意指定单词在一本书中的出现频率。
你的实现应该支持如下操作：
- WordsFrequency(book)构造函数，参数为字符串数组构成的一本书
- get(word)查询指定单词在书中出现的频率
示例：
WordsFrequency wordsFrequency = new WordsFrequency({"i", "have", "an", "apple", "he", "have", "a", "pen"});
wordsFrequency.get("you"); //返回0，"you"没有出现过
wordsFrequency.get("have"); //返回2，"have"出现2次
wordsFrequency.get("an"); //返回1
wordsFrequency.get("apple"); //返回1
wordsFrequency.get("pen"); //返回1
提示：
- book[i]中只包含小写字母
- 1 <= book.length <= 100000
- 1 <= book[i].length <= 10
- get函数的调用次数不会超过100000
解题思路与代码
这道题其实就考察了一个点，就是你对哈希表的理解怎么样。其次对于C++选手来说，考察了你对unordered_map函数的掌握程度。
掌握的程度越高，你写的代码也就越简洁，也就越高效，接着让我来带着大家看看这道题是如何用哈希法解决的吧。
方法一 哈希映射
-
首先，对于这道题来说，我们要创建一个成员遍历unordered_map<string,int>；这是因为我们要book中的每一个单词都遍历到这个map中去，只要单词出现了，对应的单词数量也就是int值，就加加
-
到了查询的时候，我们只需要返回map[word]就行，这是因为当使用下标访问一个不存在的键的同时，unordered_map会自动为该键创建一个值为0的条目。
具体的代码如下：
class WordsFrequency {
public:
unordered_map<string,int> map;
WordsFrequency(vector<string>& book) {
for(auto& a : book)
++map[a];
}
int get(string word) {
return map[word];
}
};
复杂度分析
时间复杂度
- 构造函数的时间复杂度是O(n)，因为你需要遍历一遍传入参数book，n是book中string的数量。
- 查找操作的时间复杂度是O(1)，因为unordered_map的查询操作平均时间复杂度为O(1)。
空间复杂度：
- 空间复杂度是O(n)，因为你使用了一个unordered_map来存储n个数据。
总结
这道题不是一道多难的题，其实就是在考验你是否了解哈希映射，以及对应的数据结构的用法而已。如果做的题量多了话，其实真的是分分钟秒杀的题。
最后的最后，如果你觉得我的这篇文章写的不错的话，请给我一个赞与收藏，关注我，我会继续给大家带来更多更优质的干货内容。