最大K个数问题的Python版解法总结
2019/7/13 23:30:13
本文主要是介绍最大K个数问题的Python版解法总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
TopK问题,即寻找最大的K个数,这个问题非常常见,比如从1千万搜索记录中找出最热门的10个关键词.
方法一:
先排序,然后截取前k个数.
时间复杂度:O(n*logn)+O(k)=O(n*logn)。
这种方式比较简单粗暴,提一下便是。
方法二:最大堆
我们可以创建一个大小为K的数据容器来存储最小的K个数,然后遍历整个数组,将每个数字和容器中的最大数进行比较,如果这个数大于容器中的最大值,则继续遍历,否则用这个数字替换掉容器中的最大值。这个方法的理解也十分简单,至于容器的选择,很多人第一反应便是最大堆,但是python中最大堆如何实现呢?我们可以借助实现了最小堆的heapq库,因为在一个数组中,每个数取反,则最大数变成了最小数,整个数字的顺序发生了变化,所以可以给数组的每个数字取反,然后借助最小堆,最后返回结果的时候再取反就可以了,代码如下:
import heapq def get_least_numbers_big_data(self, alist, k): max_heap = [] length = len(alist) if not alist or k <= 0 or k > length: return k = k - 1 for ele in alist: ele = -ele if len(max_heap) <= k: heapq.heappush(max_heap, ele) else: heapq.heappushpop(max_heap, ele) return map(lambda x:-x, max_heap) if __name__ == "__main__": l = [1, 9, 2, 4, 7, 6, 3] min_k = get_least_numbers_big_data(l, 3)
方法三:quick select
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)
这篇关于最大K个数问题的Python版解法总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-20Python编程入门指南
- 2024-12-20Python编程基础与进阶
- 2024-12-19Python基础编程教程
- 2024-12-19python 文件的后缀名是什么 怎么运行一个python文件?-icode9专业技术文章分享
- 2024-12-19使用python 把docx转为pdf文件有哪些方法?-icode9专业技术文章分享
- 2024-12-19python怎么更换换pip的源镜像?-icode9专业技术文章分享
- 2024-12-19Python资料:新手入门的全面指南
- 2024-12-19Python股票自动化交易实战入门教程
- 2024-12-19Python股票自动化交易入门教程
- 2024-12-18Python量化入门教程:轻松掌握量化交易基础知识