杭州网站设计公司价格,华为域名注册,网站页面优化公告,wordpress设置qq邮箱设置在海量数据中找出出现频率最好的前k个数#xff0c;或者从海量数据中找出最大的前k个数#xff0c;这类问题通常被称为top K问题。针对top K类问题#xff0c;通常比较好的方案是分治Trie树/hash小顶堆#xff08;就是上面提到的最小堆#xff09;#xff0c;即先将数据集…在海量数据中找出出现频率最好的前k个数或者从海量数据中找出最大的前k个数这类问题通常被称为top K问题。针对top K类问题通常比较好的方案是分治Trie树/hash小顶堆就是上面提到的最小堆即先将数据集按照Hash方法分解成多个小数据集然后使用Trie树或者Hash统计每个小数据集中的query词频之后用小顶堆求出每个数据集中出现频率最高的前K个数最后在所有top K中求出最终的top K。方法进阶1、最简单的方法就是快排取topk2、局部淘汰法。用一个容器保存前k个数然后将剩余的所有数字——与容器内的最小数字相比如果所有后续的元素都比容器内的k个数还小那么容器内这k个数就是最大k个数。如果某一后续元素比容器内最小数字大则删掉容器内最小元素并将该元素插入容器最后遍历完所有的数得到的结果容器中保存的数即为最终结果了3、分治法。将1亿个数据分成100份每份100万个数据找到每份数据中最大的10000个最后在剩下的100*10000个数据里面找出最大的10000个。100万个数据里面查找最大的10000个数据的方法如下用快速排序的方法将数据分为2堆如果大的那堆个数N大于10000个继续对大堆快速排序一次分成2堆如果大的那堆个数N大于10000个继续对大堆快速排序一次分成2堆如果大堆个数N小于10000个就在小的那堆里面快速排序一次找第10000-n大的数字递归以上过程就可以找到第1w大的数。参考上面的找出第1w大数字就可以类似的方法找到前10000大数字了。此种方法需要每次的内存空间为10^6*44MB一共需要101次这样的比较。4、采用最小堆。首先读入前10000个数来创建大小为10000的最小堆建堆的时间复杂度为Omlogmm为数组的大小即为10000然后遍历后续的数字并于堆顶最小数字进行比较。如果比最小的数小则继续读取后续数字如果比堆顶数字大则替换堆顶元素并重新调整堆为最小堆。整个过程直至1亿个数全部遍历完为止。然后按照中序遍历的方式输出当前堆中的所有10000个数字。该算法的时间复杂度为Onmlogm空间复杂度是10000常数。以下是一些经常被提及的该类问题。1有10000000个记录这些查询串的重复度比较高如果除去重复后不超过3000000个。一个查询串的重复度越高说明查询它的用户越多也就是越热门。请统计最热门的10个查询串要求使用的内存不能超过1GB。2有10个文件每个文件1GB每个文件的每一行存放的都是用户的query每个文件的query都可能重复。按照query的频度排序。3有一个1GB大小的文件里面的每一行是一个词词的大小不超过16个字节内存限制大小是1MB。返回频数最高的100个词。4提取某日访问网站次数最多的那个IP。510亿个整数找出重复次数最多的100个整数。6搜索的输入信息是一个字符串统计300万条输入信息中最热门的前10条每次输入的一个字符串为不超过255B内存使用只有1GB。7有1000万个身份证号以及他们对应的数据身份证号可能重复找出出现次数最多的身份证号。最小堆对于每个非叶子节点的数值一定不大于孩子节点的数值。这样可用含有K个节点的最小堆来保存K个目前的最大值(当然根节点是其中的最小数值)。每次有数据输入的时候可以先与根节点比较。若不大于根节点则舍弃否则用新数值替换根节点数值。并进行最小堆的调整。Python 小顶堆class solution:def topk(self, inputs, k):import heapqif inputs None or len(inputs) k or len(inputs) 0 or k 0:# 注意极限条件的确定return []output []for number in inputs:if len(output) k:output.append(number)else:output heapq.nlargest(k, output)print(output)if number output[-1]:output[-1] numberelse:continuereturn output
