这是一个创建于 894 天前的主题，其中的信息可能已经有所发展或是发生改变。
生产中需要用到相关实现算法，感觉比较像一道算法题，但我想了想没有什么太好的办法，来请教一下万能的 v 友。
现有一自然数 N ，假定取值范围 1-100.
有一数组，储存双精度浮点数，数组长度为 N-100000.求筛选数组中最大（或最小）前 N 位数所在的位置。
为传统算法基本上都是为全排序设计的，不存在说只取前 N 位最大即可。还有一个问题是排序大多数直接操作数据而不是操作指针，给我整不会了。。
需要时间复杂度最优，不在意空间复杂度。。
12 条回复 • 2022-06-17 11:13:01 +08:00
 |
1
vance123 2022-06-16 23:00:43 +08:00 via Android
关键词 heap
|
 |
2
ipwx 2022-06-16 23:01:02 +08:00  1
快速选择，做一半的快速排序，期望复杂度 O(n)
先做一次快速排序，若轴枢元素是第 K 大。 * 如果 K < N 则对右侧做 N-K 的快速划分。 * 如果 K > N 则对左侧做 N 的快速划分。 |
 |
3
per 2022-06-16 23:01:13 +08:00 via iPhone
最大（小）堆排序
|
|
4
ipwx 2022-06-16 23:02:57 +08:00
哦最大最小堆也挺好，可以处理在线情况。
换个几号吧，如果你的全数组长度是 M ，用最小堆找最大的前 N 个元素，那么时间复杂度就是 O(M log N)。 反之用最大堆可以找最小的 N 个元素。 |
 |
5
ynyounuo 2022-06-16 23:05:08 +08:00 via iPhone
经典 topk 算法不是全网各处都有
|
 |
6
dbsquirrel 2022-06-16 23:05:55 +08:00 via iPhone
Quick Select?
|
 |
7
sunjourney 2022-06-17 00:47:06 +08:00
大顶堆不就是吗，最常见的算法
|
 |
8
msg7086 2022-06-17 06:04:53 +08:00
容量 N 的大顶堆。要带位置的话元素里加上位置信息即可。
|
 |
9
rabbbit 2022-06-17 08:50:22 +08:00 1
堆排序
 |
 |
10
radiocontroller 2022-06-17 09:23:10 +08:00
堆排序和快排，快排不稳定，最差情况 O(N^2)
|
 |
11
anonymousar 2022-06-17 09:53:17 +08:00 1
明显 bfptr 更好 一堆说 heap 是啥意思
|
 |
12
Erroad 2022-06-17 11:13:01 +08:00
@anonymousar #10 没学过呗，我也第一次听说
|
Select Language