黑松山资源网 Design By www.paidiu.com
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)
黑松山资源网 Design By www.paidiu.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
黑松山资源网 Design By www.paidiu.com
暂无评论...
更新日志
2024年10月09日
2024年10月09日
- s14全球总决赛瑞士轮什么时候开始 s14瑞士轮开始时间介绍
- 晨报|《使命召唤21》全球发布预告 《异形:隔离》续作官宣开发中
- 隐形女联动毁灭博士?杰西卡·阿尔巴与小唐尼晒合影
- 《博德之门3》7号补丁发布后:Mod下载量达到2200万次!
- 徐璨宾《井底的蚯蚓》[FLAC/分轨][218.37MB]
- 王冰冰《Vaga Luna 月球漫游》[320K/MP3][62.76MB]
- 证声音乐图书馆《蔚蓝海岸·爵士度假日》[320K/MP3][59.79MB]
- 群星.1993-飞图合唱歌曲精丫飞图】【WAV+CUE】
- 王霏霏.2024-TOOOOO.BUSY(EP)【SNMUSIC】【FLAC分轨】
- 张宇.2016-好男人的情歌NEWXRCD【金牌大风】【WAV+CUE】
- 《食戟之灵》小林龙胆兔女郎比基尼版模型即将发售
- 重大里程碑!九号电动第500万台智能两轮电动车正式下线
- TGA主持人发文祝贺《暗喻幻想》 国外网友:提名稳了?
- 【原神】V5.0攻略 | 旋曜玉帛收集攻略(序号81~序号90)
- 【原神】V5.0攻略 | 旋曜玉帛收集攻略(序号91~序号100)