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

原创
2016/11/26 09:59
阅读数 408

如果只需要查询一次, 那就直接做;如果要多次查询,而且要查询各种不同的单词,那就先预处理一遍, 接下来就只需要用O(1)的时间进行查询。

只查询一次

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

多次查询

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

 

package com.NodePair;
import java.util.HashMap;

public class Frequency {
HashMap<String,Integer> setupDictionary(String[] book)
{
HashMap<String,Integer> table=new HashMap<String,Integer>();
for(String s:book)
{
s=s.toLowerCase();
if(!table.containsKey(s))
{
table.put(s,0);
}
table.put(s, table.get(s)+1);
}
return table;
}


int getFrequency(HashMap<String,Integer> table,String word)
{
if(table==null||word==null)
return -1;
word=word.toLowerCase();
if(table.containsKey(word))
{
return table.get(word);
}
return 0;
}
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部