最大K个数问题的Python版解法总结

yipeiwu_com6年前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) 

相关文章

pandas中DataFrame修改index、columns名的方法示例

一般常用的有两个方法: 1、使用DataFrame.index = [newName],DataFrame.columns = [newName],这两种方法可以轻松实现。 2、使用...

python实现自主查询实时天气

python实现自主查询实时天气

本文实例为大家分享了python实现自主查询实时天气的具体代码,供大家参考,具体内容如下 用到了urllib2 json  很简单的一个应用 如下 获取城市编号 #cod...

Python中if __name__ == '__main__'作用解析

当你打开一个.py文件时,经常会在代码的最下面看到if __name__ == '__main__':,现在就来介 绍一下它的作用.     &n...

跟老齐学Python之Python文档

跟老齐学Python之Python文档

文档很重要。独孤九剑的剑诀、易筋经的心法、写着辟邪剑谱的袈裟,这些都是文档。连那些大牛人都要这些文档,更何况我们呢?所以,文档是很重要的。 文档,说白了就是用word(这个最多了)等(注...

在flask中使用python-dotenv+flask-cli自定义命令(推荐)

最近在重构 flask 项目的时候发现项目的环境变量异常的混乱,非常不便于管理。而且,更重要的事情是我需要通过自定义命令来运行 devlopment 和 p...