1
lhx2008 2018-03-25 14:06:00 +08:00 via Android 1
维护一个 k 大小的最小堆
|
3
clearbug 2018-03-25 14:16:49 +08:00 via Android
利用快排的思维
|
4
Andiry 2018-03-25 14:19:14 +08:00
QuickSort partition
|
6
aidaizyy 2018-03-25 15:10:01 +08:00
不考虑顺序的话,没必要用最小堆,用快排思想就可以了,时间复杂度要低一些。
|
7
zjp 2018-03-25 15:18:08 +08:00 via Android
正在做 LeetCode 215.Kth Largest Element in An array
才发现上学期刚学过快速选择… |
8
gbin OP @wjm2038 最小堆就是一种有序的完全二叉树,父结点总是不小于子结点。你可以看一下 wikipedia https://zh.wikipedia.org/zh-hans/%E6%9C%80%E5%A4%A7%E2%80%94%E6%9C%80%E5%B0%8F%E5%A0%86
|
9
mrcn 2018-03-25 17:44:50 +08:00 via Android
堆应该是 O(kLog n),快排思想应该也是这个?
|
10
GGGG430 2018-03-25 17:47:19 +08:00 via iPhone
快排倒叙取 topk/小顶堆 /维护一个大小为 k 的数组
|
11
stevenbipt 2018-03-25 17:53:17 +08:00 via Android
top k 问题⊙▽⊙才在算法导论上学了这个算法,当初自己没学这个的时候就直接排序然后找到最大的数字输出然后删除最大的数字,然后继续找出来最大输出然后删除,这样进行 k 次
|
12
stevenbipt 2018-03-25 17:56:18 +08:00 via Android
这个问题不要求排序直接用快速排序的思想效率应该是相对比较高的
|
13
victor97 2018-03-25 19:14:56 +08:00 via Android
快排的思路,时间复杂度是 O(n)的
|