20180325 今日算法

[gbin]

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

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

[lhx2008]

维护一个 k 大小的最小堆

[gbin]

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

[clearbug]

利用快排的思维

[Andiry]

QuickSort partition

[wjm2038]

@gbin 请问下最小堆是啥啊

[aidaizyy]

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

[zjp]

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

[gbin]

@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]

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

[GGGG430]

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

[stevenbipt]

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

[stevenbipt]

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

[victor97]

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