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

高洛峰

发布时间：2017-03-02 11:16:16

1450人浏览过

来源于php中文网

原创

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)

立即学习“Python免费学习笔记（深入）”；

方法三：quick select

php商城系统

PHP商城系统是国内功能优秀的网上商城系统，同时也是一个商业的PHP开发框架，有多套免费模版，强大的后台管理功能，专业的网上商城系统解决方案，快速建设网上购物商城、数码商城、手机商城、办公用品商城等网站。 php商城系统v3.0 rc6升级 1、主要修复用户使用中出现的js未加载完报错问题，后台整改、以及后台栏目的全新部署、更利于用户体验。 2、扩展出，更多系统内部的功能，以便用户能够迅速找到需

下载

quick select算法.其实就类似于快排.不同地方在于quick select每趟只需要往一个方向走.
时间复杂度:O(n).

def qselect(A,k): 
  if len(A)=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更多最大K个数问题的Python版解法相关文章请关注PHP中文网！

立即学习“Python免费学习笔记（深入）”；

PyTorch 中的广播机制与矩阵乘法：彻底厘清常见混淆

Python 中按位与运算符（&）的对齐规则详解

如何为带尺寸标注的数组类型创建别名

Python字典系统学习路线第3讲_核心原理与实战案例详解【指导】

Python 中链式赋值 a = b = c 的行为与字典操作详解

python速学教程(入门到精通)

python怎么学习？python怎么入门？python在哪学？python怎么学才快？不用担心，这里为大家提供了python速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！

下载

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：Python中global语句下全局变量的值的修改下一篇：Python中的多行注释文档编写风格

作者最新文章

实现一个 Java 版的 Redis

2018-05-30 13:56

Asp.net使用SignalR实现发送图片

2018-05-28 16:22

HTML5:使用Canvas实时处理Video

2018-05-28 17:58

最简单的微信小程序Demo

2018-05-30 10:20

Python构造自定义方法来美化字典结构输出

2018-05-29 10:33

html设置加粗、倾斜、下划线、删除线等字体效果示例介绍

2018-05-31 09:48

微信小程序：如何实现tabs选项卡效果示例

2018-05-29 15:01

微信小程序开发教程-App()和Page()函数概述

2018-05-28 16:19

python中pandas.DataFrame（创建、索引、增添与删除）的简单操作方法介绍

2018-05-29 15:23

详解python redis使用方法

2018-05-28 15:01

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI大模型

开放平台

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI大模型

腾讯元宝

腾讯混元平台推出的AI助手

文档处理

Excel 表格

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI大模型

中文写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

中文写作

写作工具

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接

图画生成

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI大模型

中文写作

智谱清言 - 免费全能的AI助手

AI大模型

PDF 文档

相关专题

javascript void运算符

void是一元运算符，执行右侧表达式但始终返回undefined；用于丢弃返回值、阻止a标签跳转、IIFE忽略结果、动态导入不取Promise、安全获取undefined。本专题为大家提供相关的文章、下载、课程内容，供大家免费下载体验。

2025.12.29

vscode的界面字体大小调整

调整VSCode界面字体大小可通过设置编辑器或整体UI缩放实现；2.修改"Editor:FontSize"改变代码字体；3.设置"Window:ZoomLevel"调整整体界面字体；4.使用Ctrl+滚轮快捷键临时缩放。本专题为大家提供相关的文章、下载、课程内容，供大家免费下载体验。

2025.12.29

VSCode的注释快捷键

单行注释快捷键为Ctrl+/（Windows/Linux）或Cmd+/（macOS），块注释使用Shift+Alt+A（Windows/Linux）或Shift+Option+A（macOS），VSCode会根据语言类型自动匹配语法，如JavaScript用//，Python用#，C++用//，若快捷键无效需检查语言扩展或插件冲突。本专题为大家提供相关的文章、下载、课程内容，供大家免费下载体验。

2025.12.29