最大K个数问题的Python版解法总结
TopK问题,即寻找最大的K个数,这个问题非常常见,比如从1千万搜索记录中找出最热门的10个关键词.
方法一:
先排序,然后截取前k个数.
时间复杂度:O(n*logn)+O(k)=O(n*logn)。
这种方式比较简单粗暴,提一下便是。
方法二:最大堆
我们可以创建一个大小为K的数据容器来存储最小的K个数,然后遍历整个数组,将每个数字和容器中的最大数进行比较,如果这个数大于容器中的最大值,则继续遍历,否则用这个数字替换掉容器中的最大值。这个方法的理解也十分简单,至于容器的选择,很多人第一反应便是最大堆,但是python中最大堆如何实现呢?我们可以借助实现了最小堆的heapq库,因为在一个数组中,每个数取反,则最大数变成了最小数,整个数字的顺序发生了变化,所以可以给数组的每个数字取反,然后借助最小堆,最后返回结果的时候再取反就可以了,代码如下:
importheapq defget_least_numbers_big_data(self,alist,k): max_heap=[] length=len(alist) ifnotalistork<=0ork>length: return k=k-1 foreleinalist: ele=-ele iflen(max_heap)<=k: heapq.heappush(max_heap,ele) else: heapq.heappushpop(max_heap,ele) returnmap(lambdax:-x,max_heap) if__name__=="__main__": l=[1,9,2,4,7,6,3] min_k=get_least_numbers_big_data(l,3)
方法三:quickselect
quickselect算法.其实就类似于快排.不同地方在于quickselect每趟只需要往一个方向走.
时间复杂度:O(n).
defqselect(A,k): iflen(A)<k:returnA pivot=A[-1] right=[pivot]+[xforxinA[:-1]ifx>=pivot] rlen=len(right) ifrlen==k: returnright ifrlen>k: returnqselect(right,k) else: left=[xforxinA[:-1]ifx<pivot] returnqselect(left,k-rlen)+right foriinrange(1,10): printqselect([11,8,4,1,5,2,7,9],i)