python - 设计一个算法，找出书中最常用的单词

Question

一道面试题:

找出书中最常用的单词。

我的想法:

使用哈希表，遍历并标记哈希表。

如果已知这本书的大小，如果发现任何单词被使用> 50%，则在接下来的遍历中跳过任何新单词，只计算旧单词。如果书籍尺寸未知怎么办？

是O(n)和O(n)的时间和空间。

有什么更好的主意吗？

谢谢

Answer 1

要确定复杂性，我认为您需要考虑两个变量，n = 单词总数，m = 唯一单词数。我想最好的情况复杂度将接近 O(n log(m)) 速度和 O(m) 存储，假设每次迭代 n 个单词中的每一个，并基于哈希表构建和搜索或其他最终包含 m 个元素的结构。