Cracking the coding interview--Q19.8

Cracking the coding interview--Q19.8

Design a method to find the frequency of occurrences of any given word in a book.

译文：

设计一个函数，找到给定单词在一本书中的出现次数。

解答

这道题目和19.2是一个思路。如果只需要查询一次， 那就直接做；如果要多次查询，而且要查询各种不同的单词，那就先预处理一遍， 接下来就只需要用O(1)的时间进行查询。

只查询一次

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

多次查询

如果我们要对一本书进行多次的查询，就可以遍历一次这本书的单词， 把它出现的次数存入哈希表中。查询的时候即可用O(1)的时间完成。

Read full article from Cracking the coding interview--Q19.8