问题:
从300万字符串中找到最热门的10条搜索的输入信息是一个字符串,统计300万输入信息中的最热门的前10条,我们每次输入的一个字符串为不超过255byte,内存使用只有1G。请描述思想,写出算法(c语言),空间和时间复杂度。
答案:
300万个字符串最多(假设没有重复,都是最大长度)占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理。
可以使用key为字符串(事实上是字符串的hash值),值为字符串出现次数的hash来统计每个字符串出现的次数。
并用一个长度为K的堆来的数组/链表存储目前出现次数最多的10个字符串。