最大K个数问题的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)
赞 (0)

相关推荐

  • python获取局域网占带宽最大3个ip的方法

    python获取局域网占带宽最大3个ip的方法

    本文实例讲述了python获取局域网占带宽最大3个ip的方法.分享给大家供大家参考.具体实现方法如下: import re import urllib url = 'http://admin:netcenter@192.168.0.1/analyze.cgi?page=1&px=3&sf=1' a = urllib.urlopen(url).read() ip = re.findall(r'192\.168\.\d+\.\d+', a, re.M) ip1 = ip[0] ip2 = ip

  • python计算最大优先级队列实例

    复制代码 代码如下: # -*- coding: utf-8 -*- class Heap(object): @classmethod    def parent(cls, i):        """父结点下标"""        return int((i - 1) >> 1); @classmethod    def left(cls, i):        """左儿子下标""

  • 使用Python求解最大公约数的实现方法

    1. 欧几里德算法 欧几里德算法又称辗转相除法, 用于计算两个整数a, b的最大公约数.其计算原理依赖于下面的定理: 定理: gcd(a, b) = gcd(b, a mod b) 证明:   a可以表示成a = kb + r, 则r = a mod b   假设d是a, b的一个公约数, 则有  d|a, d|b, 而r = a - kb, 因此d|r.   因此,d是(b, a mod b)的公约数.   加上d是(b,a mod b)的公约数,则d|b, d|r, 但是a = kb + r

  • python使用分治法实现求解最大值的方法

    本文实例讲述了python使用分治法实现求解最大值的方法.分享给大家供大家参考.具体分析如下: 题目: 给定一个顺序表,编写一个求出其最大值和最小值的分治算法. 分析: 由于顺序表的结构没有给出,作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义,数据随机生成.我们知道如果数组大小为 1 则可以直接给出结果,如果大小为 2则一次比较即可得出结果,于是我们找到求解该问题的子问题即: 数组大小 <= 2.到此我们就可以进行分治运算了,只要求解的问题数组长度比 2 大就继续分治,否则求解子问题

  • python获取一组数据里最大值max函数用法实例

    本文实例讲述了python获取一组数据里最大值max函数用法.分享给大家供大家参考.具体如下: # 最简单的 max(1, 2) max('a', 'b') # 也可以对列表和元组使用 max([1,2]) max((1,2)) # 还可以指定comparator function max('ah', 'bf', key=lambda x: x[1]) def comparator(x): return x[1] max('ah', 'bf', key=comparator) 希望本文所述对大家

  • Python实现求最大公约数及判断素数的方法

    本文实例讲述了Python实现求最大公约数及判断素数的方法.分享给大家供大家参考.具体实现方法如下: #!/usr/bin/env python def showMaxFactor(num): count = num / 2 while count > 1: if num % count == 0: print 'largest factor of %d is %d' % (num, count) break #break跳出时会跳出下面的else语句 count -= 1 else: prin

  • Python中用max()方法求最大值的介绍

    max() 方法返回其参数最大值:最接近正无穷大的值. 语法 以下是max()方法的语法: max( x, y, z, .... ) 参数 x -- 这是一个数值表达式. y -- 这也是一个数值表达式. z -- 这是一个数值表达式. 返回值 此方法返回其参数的最大值. 例子 下面的例子显示了max()方法的使用. #!/usr/bin/python print "max(80, 100, 1000) : ", max(80, 100, 1000) print "max(-

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

    TopK问题,即寻找最大的K个数,这个问题非常常见,比如从1千万搜索记录中找出最热门的10个关键词. 方法一: 先排序,然后截取前k个数. 时间复杂度:O(n*logn)+O(k)=O(n*logn). 这种方式比较简单粗暴,提一下便是. 方法二:最大堆 我们可以创建一个大小为K的数据容器来存储最小的K个数,然后遍历整个数组,将每个数字和容器中的最大数进行比较,如果这个数大于容器中的最大值,则继续遍历,否则用这个数字替换掉容器中的最大值.这个方法的理解也十分简单,至于容器的选择,很多人第一反应便

  • Python实现查找最小的k个数示例【两种解法】

    本文实例讲述了Python实现查找最小的k个数.分享给大家供大家参考,具体如下: 题目描述 输入n个整数,找出其中最小的K个数.例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,. 解法1 使用partition函数可以知道,使用==O(N)==的时间复杂度就可以找出第K大的数字,并且左边的数字比这个数小,右边的数字比这个数字大.因此可以取k为4,然后输出前k个数字,如果需要排序的话再对结果进行排序 # -*- coding:utf-8 -*- class So

  • JAVA中寻找最大的K个数解法

    这个题拿到之后首先会想到排序,排好序之后在选取选取最大的K个数.排序选择快速排序是个比较好的选择.好了,让我们来进行第一个解法:快速排序代码如下 复制代码 代码如下: public static void quickSort(int[] arr, int start, int end) {  if (start < end) {   int key = arr[start];   int right = start;   int left = end;   while (right < lef

  • Python找出最小的K个数实例代码

    题目描述 输入n个整数,找出其中最小的K个数.例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,. 这个题目完成的思路有很多,很多排序算法都可以完成既定操作,关键是复杂度性的考虑.以下几种思路当是笔者抛砖引玉,如果读者有兴趣可以自己再使用其他方法一一尝试. 思路1:利用冒泡法 临近的数字两两进行比较,按照从小到大的顺序进行交换,如果前面的值比后面的大,则交换顺序.这样一趟过去后,最小的数字被交换到了第一位:然后是次小的交换到了第二位,...,依次直到第k个数,停

  • Python实现从N个数中找到最大的K个数

    提出问题: 如何在某集合里面找出最大或最小的K个元素. 解决思路: 找出最大或最下的K个元素,可以使用Python库中的heapq模块,该模块提供两个函数nlargest()求最大K个和nsmallest()求最小K个. 下面我们举例说明: import heapq nums=[12,-9,-3,32,9,56,23,0,11,34] print(heapq.nlargest(4,nums)) #-->最大的4个 print(heapq.nsmallest(4,nums)) #-->最小的4个

  • 基于ID3决策树算法的实现(Python版)

    基于ID3决策树算法的实现(Python版)

    实例如下: # -*- coding:utf-8 -*- from numpy import * import numpy as np import pandas as pd from math import log import operator #计算数据集的香农熵 def calcShannonEnt(dataSet): numEntries=len(dataSet) labelCounts={} #给所有可能分类创建字典 for featVec in dataSet: currentLa

  • 名片管理系统python版

    本文实例为大家分享了python名片管理系统的具体代码,供大家参考,具体内容如下 import os list_all = [] def page(): """输出主页面""" print("*" * 30) print("欢迎使用[名片管理系统]v2.0") print() print("1.新建名片") print("2.查看全部") print("3.

  • python版百度语音识别功能

    python版百度语音识别功能

    本文实例为大家分享了python版百度语音识别功能的具体代码,供大家参考,具体内容如下 环境:使用的IDE是Pycharm 1.新建工程 2.配置百度语音识别环境 "File"--"Settings"打开设置面板,"Project"标签下添加Project Interpreter,点击右侧"+" 输入"baidu-aip",进行安装 新建测试文件 from aip import AipSpeech &quo

  • python版opencv摄像头人脸实时检测方法

    OpenCV版本3.3.0,注意模型文件的路径要改成自己所安装的opencv的模型文件的路径,路径不对就会报错,一般在opencv-3.3.0/data/haarcascades 路径下 import numpy as np import cv2 face_cascade = cv2.CascadeClassifier('haarcascade_frontalface_default.xml') cap = cv2.VideoCapture(0) while True: ret,img = ca

  • Python版名片管理系统

    本文实例为大家分享了Python版名片管理系统的具体代码,供大家参考,具体内容如下 先建立cards_main的文件 import cards_tools #无限循环,由用户主动决定什么时候退出 while True: #TODO注释,用于标记需要去做的工作 cards_tools.show_menu() action_str = raw_input("请选择希望执行的操作: ") print("你选择的操作是 %s" % action_str) #1,2,3针对名

随机推荐