algorithm - 查找出现次数最多的单词

Question

搜索文档中出现次数最多的单词的最佳方法(算法)是什么？

Answer 1

查找文档中出现次数最多的单词可以在 O(n) 中通过简单的 histogram 完成[基于哈希]:

histogram <- new map<String,int>
for each word in document: 
   if word in histogram:
      histogram[word] <- histogram[word] + 1
   else:
      histogram[word] <- 1
max <- 0
maxWord<- ""
for each word in histogram:
  if histogram[word] > max:
     max <- histogram[word]
     maxWord <- word
return maxWord

这是 O(n) 的解决方案，并且由于问题显然是 Omega(n) 问题，因此它在 big O notation 方面是最优的.