(分治)输出前m大的数。。。
2024-08-30 08:12:12
描述
给定一个数组包含n个元素,统计前m大的数并且把这m个数从大到小输
出。
输入
第一行包含一个整数n,表示数组的大小。n < 100000。
第二行包含n个整数,表示数组的元素,整数之间以一个空格分开
。每个整数的绝对值不超过100000000。
第三行包含一个整数m。m < n。
输出
从大到小输出前m大的数,每个数一行。
思路:
排序后输出(nlogn)
用分治处理(n+mlogm)
关键:n时间内将前m大的都移到最右边
引入操作
arrangeRight(k) :把数组(或数组的一部分)前k大的
都弄到最右边
如何将前k大的都弄到最右边
1) 设key=a[0], 将key挪到适当位置,使得比key小的元素都在
key左边,比key大 的元素都在key右边(线性时间完成)
2) 选择 数组的前部或后部再进行arrangeRight操作
当a=k时, done
a> k 对右边a-1个元素再进行arrangeRight (k)
a< k 对左边b个元素再进行arrangeRight(k-a)
最新文章
- Android 笔记 a+b day6
- PLSQL Developer导入Excel数据
- ajax删除数据后刷新页面
- Web_add_header
- Spring 整合 Struts2
- Aquarium Cycling
- bootstrap table笔记
- MyBatis深入理解一
- 控制台打印Hibernate的SQL语句显示绑定参数值
- 安装、设置与启动MySql绿色版的方法
- eclipse maven构建
- 读论文系列:Deep transfer learning person re-identification
- Shell执行*.sql
- ubuntu16.04 npm安装
- 报错解决——OSError: libdarknet.so: cannot open shared object file: No such file or directory
- java中coroutine使用
- Xshell多版本被曝存在后门,了解紧急响应修复预案
- 转转转---js正则表达exec与match的区别说明
- 25个Java机器学习工具&;库--转载
- Java内存区域介绍