讨论一个面试很常问的TOPK的问题
面试里面TopK是很常问的问题，通常解决方法都答先将大数据集分成多个小份，然后用hash表统计频率，再维护一个小顶堆统计得出TOPK个数据，最后将多个小份分的TOPK进行合并。
那么我有一个困惑，假设我们求top10个值，那么如果在每个小份数据集中，某一个词都排在第11个，如果合并每个小份数据集的TOP11的话，这个词是可以进入总的TOP10的，那么怎么解决这个问题呢？
还是我哪个步骤错了？
PS:很多人没听懂，我举个例子吧，假设有一本非常非常大的书，一共有10000册，你没办法用一台计算机去处理它，我们要求这本书出现最多的10个单词，那么按分治法，我们把1-100册放到机器1进行hash表统计词的频率，维护一个大小为10的小顶堆，我们用100台机器维护100个小顶堆，并在最后对这100个小顶堆进行排序，得出TOP 10的单词。。但是如果每一台机器的第十一个词都是kitty，那么很可能kitty也应该进入top10。那这样的情况应该怎么处理，是哪个步骤出了问题？是不是分词的时候不能直接按册分，要遍历这10000册，对每个单词进行hash？感觉不是太好啊。。求教
不知道我表达清楚没。。
腾讯开奖299人在聊
投递快手等公司7个岗位 >