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

 更新时间:2016年06月16日 18:09:39   作者:mattkang   我要评论

这篇文章主要介绍了最大K个数问题的Python版解法总结,以最大K个数问题为基础的算法题目在面试和各大考试及竞赛中经常出现,需要的朋友可以参考下

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 获取div标签中的文字实例

    Python 获取div标签中的文字实例

    今天小编就为大家分享一篇Python 获取div标签中的文字实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2018-12-12
  • 快速了解Python中的装饰器

    快速了解Python中的装饰器

    这篇文章主要介绍了快速了解Python中的装饰器,具有一定借鉴价值,需要的朋友可以参考下
    2018-01-01
  • Python序列化基础知识(json/pickle)

    Python序列化基础知识(json/pickle)

    这篇文章主要为大家详细介绍了Python序列化json和pickle基础知识,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
    2017-10-10
  • Python设计模式之代理模式实例

    Python设计模式之代理模式实例

    这篇文章主要介绍了设计模式中的代理模式Python实例,需要的朋友可以参考下
    2014-04-04
  • python 提取文件的小程序

    python 提取文件的小程序

    在做网站项目时,开发经常要给工程一个升级包,包含本次修改的内容,这个升级包的内容就是tomcat的发布目录下的文件;
    2009-07-07
  • Python中decorator使用实例

    Python中decorator使用实例

    这篇文章主要介绍了Python中decorator使用实例,本文讲解了如何调用decorator、decorator函数的定义、decorator的应用场景等内容,需要的朋友可以参考下
    2015-04-04
  • Python异常处理操作实例详解

    Python异常处理操作实例详解

    这篇文章主要介绍了Python异常处理操作,结合实例形式分析了Python常见的异常处理类型、相关操作技巧与注意事项,需要的朋友可以参考下
    2018-08-08
  • Python运维自动化之nginx配置文件对比操作示例

    Python运维自动化之nginx配置文件对比操作示例

    这篇文章主要介绍了Python运维自动化之nginx配置文件对比操作,涉及Python针对文件的读取、遍历、比较进而达到差异对比的相关操作技巧,需要的朋友可以参考下
    2018-08-08
  • Python实现控制台中的进度条功能代码

    Python实现控制台中的进度条功能代码

    下面小编就为大家分享一篇Python实现控制台中的进度条功能代码,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2017-12-12
  • Python实现字典的遍历与排序功能示例

    Python实现字典的遍历与排序功能示例

    这篇文章主要介绍了Python实现字典的遍历与排序功能,结合实例形式分析了Python字典的遍历与排序相关函数与使用技巧,需要的朋友可以参考下
    2017-12-12

最新评论