南强小屋 Design By 杰米
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)
标签：
Python,最大K个数,算法
南强小屋 Design By 杰米
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
南强小屋 Design By 杰米
暂无最大K个数问题的Python版解法总结的评论...
P70系列延期，华为新旗舰将在下月发布
3月20日消息，近期博主@数码闲聊站 透露，原定三月份发布的华为新旗舰P70系列延期发布，预计4月份上市。
而博主@定焦数码 爆料，华为的P70系列在定位上已经超过了Mate60，成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢？
根据目前爆料的消息来看，华为P70系列将推出三个版本，其中P70和P70 Pro采用了三角形的摄像头模组设计，而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智，但辨识度绝对拉满。