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

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

相关文章

pycharm重置设置,恢复默认设置的方法

pycharm重置设置,恢复默认设置的方法

window 系统 找到下方目录-->删除. 再重新打开pycharm # Windows Vista, 7, 8, 10: <SYSTEM DRIVE>\User...

深入理解Python单元测试unittest的使用示例

深入理解Python单元测试unittest的使用示例

软件测试 大型软件系统的开发是一个很复杂的过程,其中因为人的因素而所产生的错误非常多,因此软件在开发过程必须要有相应的质量保证活动,而软件测试则是保证质量的关键措施。正像软件熵(soft...

Python实现在tkinter中使用matplotlib绘制图形的方法示例

Python实现在tkinter中使用matplotlib绘制图形的方法示例

本文实例讲述了Python实现在tkinter中使用matplotlib绘制图形的方法。分享给大家供大家参考,具体如下: 一. 代码: # coding=utf-8 import s...

python3实现在二叉树中找出和为某一值的所有路径(推荐)

python3实现在二叉树中找出和为某一值的所有路径(推荐)

请写一个程序创建一棵二叉树,并按照一定规则,输出二叉树根节点到叶子节点的路径。 规则如下: 1、从最顶端的根结点,到最下面的叶子节点,计算路径通过的所有节点的和,如果与设置的某一值的相同...

举例简单讲解Python中的数据存储模块shelve的用法

shelve类似于一个key-value数据库,可以很方便的用来保存Python的内存对象,其内部使用pickle来序列化数据,简单来说,使用者可以将一个列表、字典、或者用户自定义的类实...