20180325 今日算法

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2461 天前的主题，其中的信息可能已经有所发展或是发生改变。

输出数组 s 前 k 个大的元素（ k 不大于数组的长度）

如:
s =[4,2,8,3,6,5],k=3
则输出
6,5，8(输出顺序不必考虑)

输出

算法

顺序

长度

13 条回复 • 2018-03-25 19:14:56 +08:00

lhx2008

2018-03-25 14:06:00 +08:00 via Android

维护一个 k 大小的最小堆

gbin

2018-03-25 14:09:54 +08:00 via Android

@lhx2008 正解。想起有一次面试问我这个题，我说了思路，那时候最小堆还真写不出来。

clearbug

2018-03-25 14:16:49 +08:00 via Android

利用快排的思维

Andiry

2018-03-25 14:19:14 +08:00

QuickSort partition

wjm2038

2018-03-25 14:57:57 +08:00 via Android

@gbin 请问下最小堆是啥啊

aidaizyy

2018-03-25 15:10:01 +08:00

不考虑顺序的话，没必要用最小堆，用快排思想就可以了，时间复杂度要低一些。

zjp

2018-03-25 15:18:08 +08:00 via Android

正在做 LeetCode 215.Kth Largest Element in An array
才发现上学期刚学过快速选择…

gbin

2018-03-25 15:57:55 +08:00 via Android

@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

mrcn

2018-03-25 17:44:50 +08:00 via Android

堆应该是 O(kLog n)，快排思想应该也是这个？

GGGG430

2018-03-25 17:47:19 +08:00 via iPhone

快排倒叙取 topk/小顶堆 /维护一个大小为 k 的数组

stevenbipt

2018-03-25 17:53:17 +08:00 via Android

top k 问题⊙▽⊙才在算法导论上学了这个算法，当初自己没学这个的时候就直接排序然后找到最大的数字输出然后删除最大的数字，然后继续找出来最大输出然后删除，这样进行 k 次

stevenbipt

2018-03-25 17:56:18 +08:00 via Android

这个问题不要求排序直接用快速排序的思想效率应该是相对比较高的

victor97

2018-03-25 19:14:56 +08:00 via Android

快排的思路，时间复杂度是 O(n)的