首页 > 代码库 > 飘逸的python - 大数据TopK问题的quick select解法
飘逸的python - 大数据TopK问题的quick select解法
TopK问题,即寻找最大的K个数,这个问题非常常见,比如从1千万搜索记录中找出最热门的10个关键词.
方法一:
先排序,然后截取前k个数.
时间复杂度:O(n*logn)+O(k)=O(n*logn)。
方法二:
最小堆.
维护容量为k的最小堆.根据最小堆性质,堆顶一定是最小的,如果小于堆顶,则直接pass,如果大于堆顶,则替换掉堆顶,并heapify整理堆,其中heapify的时间复杂度是logk.
时间复杂度:O(k+(n-k)*logk)=O(n*logk)
方法三:
本文的主角.quick select算法.其实就类似于快排.不同地方在于quick select每趟只需要往一个方向走.
时间复杂度:O(n).
def qselect(A,k): if len(A)<k:return A pivot = A[-1] right = [pivot] + [x for x in A[:-1] if x>=pivot] rlen = len(right) if rlen==k: return right if rlen>k: return qselect(right, k) else: left = [x for x in A[:-1] if x<pivot] return qselect(left, k-rlen) + right for i in range(1, 10): print qselect([11,8,4,1,5,2,7,9], i)
飘逸的python - 大数据TopK问题的quick select解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。