原文见：https://mp.weixin.qq.com/s/g4Y6ES4eL9cKJKkSpGZFYg

顺序统计之第K大元素

问题

Given an array and a number k where k is smaller than size of array, we need to find the k’th smallest element in the given array. It is given that ll array elements are distinct.

解法

对数据进行排序

时间复杂度：O(N Log N)

借助一个大小为N的最大堆，然后extractMax k次

时间复杂度：O(kLogN)

借助一个大小为K的最小堆

时间复杂度：O(NLogK)

空间复杂度：O(K)

利用快排的partition函数，将数组分为两部分，大小分别为i以及n-i（假设i>k) ;问题转换为数组arr[0, i]中取第K-i大元素

时间复杂度：平均 O（N）；最坏O(N^2)

随机版本的quickSelect

时间复杂度：期望O(N) 最坏依旧是O(N^2)

每5个为一组，并取其中位数；然后在中位数中取出pivot;

时间复杂度：最坏O(N)

总结

快排思想很重要

快排partition函数的优化思想更重要（随机化，分组取中法）

TopK问题的经典解法可以靠堆来解决