Cracking the coding interview--Q19.8

February 22, 2013
作者:Hawstein
出处:http://hawstein.com/posts/19.8.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

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)的时间完成。

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview