设计算法,找到书中最常用的单词

Question

面试问题:

找到书中最常用的单词.

我的想法:

使用哈希表,遍历并标记哈希表.

如果已知书的大小,如果发现任何单词的使用率> 50%,则跳过以下遍历中的任何新单词并仅计算旧单词.如果图书大小未知怎么办？

它是O(n)和O(n)的时间和空间.

有更好的想法吗？

谢谢

Answer 1

通常，当我们必须确定最多/最少使用的东西时，堆是非常适合的数据结构。

甚至用于这些目的的Python Counter.nlargest也是通过堆数据结构实现的。

二叉堆数据结构具有以下复杂性

CreateHeap - O(1)
FindMin - O(1)
deleteMin - O(logn)
Insert - O(logn)

我对哈希（在 Python 中使用默认字典）和堆（在 Python 中使用 Collections.Counter.nlargest）进行了比较，哈希比堆稍好一些。

>>> stmt1="""
import collections, random
somedata=[random.randint(1,1000) for i in xrange(1,10000)]
somehash=collections.defaultdict(int)
for d in somedata:
    somehash[d]+=1
maxkey=0
for k,v in somehash.items():
    if somehash[maxkey] > v:
        maxkey=k
"""
>>> stmt2="""
import collections,random
somedata=[random.randint(1,1000) for i in xrange(1,10000)]
collections.Counter(somedata).most_common(1)
"""
>>> t1=timeit.Timer(stmt=stmt1)
>>> t2=timeit.Timer(stmt=stmt2)
>>> print "%.2f usec/pass" % (1000000 * t2.timeit(number=10)/10)
38168.96 usec/pass
>>> print "%.2f usec/pass" % (1000000 * t1.timeit(number=10)/10)
33600.80 usec/pass