当前位置: 首页 > news >正文

[经典] 在未排序数组中返回topK大的数

解法一,排序

先从大到小快排,然后扫前K个返回

时间复杂度:O(NlogN),空间复杂度O(1)

解法二,优先队列

前K个放入优先队列中,与最小堆顶元素比较大小,若大于则删除堆顶并插入;否则跳过

时间复杂度:O(NlogK),空间复杂度O(K)

解法三,堆调整

先将数组直接用完全二叉树存储,复杂度O(N);然后对树进行堆调整,调整为最大堆,复杂度不超过O(2N)(对每一层的操作总次数进行分析);最后弹出K个堆顶元素,复杂度不超过O(KlogN)。由于K比N小得多,复杂度为O(N)

时间复杂度:O(N),空间复杂度也是O(N)

转载于:https://www.cnblogs.com/littletail/p/5240277.html

相关文章:

  • Android Studio第一次启动的Fetching android sdk component information的问题
  • Android 代码中文字在手机上显示乱码问题解决方法
  • Java实现不同的类的属性之间相互赋值
  • 浅析python 中__name__ = '__main__' 的作用
  • MySQL常见错误
  • EL表达式里面fn的用法
  • 时间Date的各种获取方式
  • docker学习笔记1:docke环境的查看
  • Guava缓存值CacheBuilder介绍
  • android 文件存储SharedPreferences
  • Java中Cloneable 和 clone()的总结和使用
  • Java并发编程之ConcurrentHashMap原理分析
  • Could not calculate build plan: Plugin org.apache.maven.plugins:maven-resources-plugin:2.5 or one of
  • 创建表--自动编号字段且自增
  • No plugin found for prefix 'jetty' in the current project and in the plugin groups [org.apache.mave
  • 【译】JS基础算法脚本:字符串结尾
  • 【mysql】环境安装、服务启动、密码设置
  • 【跃迁之路】【585天】程序员高效学习方法论探索系列(实验阶段342-2018.09.13)...
  • ES6--对象的扩展
  • exports和module.exports
  • linux学习笔记
  • SQLServer之创建数据库快照
  • SwizzleMethod 黑魔法
  • 从零开始的webpack生活-0x009:FilesLoader装载文件
  • 番外篇1:在Windows环境下安装JDK
  • 汉诺塔算法
  • 聊聊flink的BlobWriter
  • 浅谈Golang中select的用法
  • 浅析微信支付:申请退款、退款回调接口、查询退款
  • 日剧·日综资源集合(建议收藏)
  • 如何设计一个微型分布式架构?
  • 双管齐下,VMware的容器新战略
  • 文本多行溢出显示...之最后一行不到行尾的解决
  • 《天龙八部3D》Unity技术方案揭秘
  • 400多位云计算专家和开发者,加入了同一个组织 ...
  • kubernetes资源对象--ingress
  • 组复制官方翻译九、Group Replication Technical Details
  • ​ArcGIS Pro 如何批量删除字段
  • ​secrets --- 生成管理密码的安全随机数​
  • # 安徽锐锋科技IDMS系统简介
  • (10)STL算法之搜索(二) 二分查找
  • (31)对象的克隆
  • (ResultSet.TYPE_SCROLL_INSENSITIVE,ResultSet.CONCUR_READ_ONLY)讲解
  • (二)windows配置JDK环境
  • (分布式缓存)Redis哨兵
  • (附源码)spring boot公选课在线选课系统 毕业设计 142011
  • (附源码)ssm教师工作量核算统计系统 毕业设计 162307
  • (附源码)ssm考生评分系统 毕业设计 071114
  • (三)docker:Dockerfile构建容器运行jar包
  • (一)使用IDEA创建Maven项目和Maven使用入门(配图详解)
  • (转)Sql Server 保留几位小数的两种做法
  • (转)菜鸟学数据库(三)——存储过程
  • (转)真正的中国天气api接口xml,json(求加精) ...
  • .NET C# 使用 SetWindowsHookEx 监听鼠标或键盘消息以及此方法的坑
  • .NET CF命令行调试器MDbg入门(一)