文章目录

1. 1. Kth Largest Element in an Array

Kth Largest Element in an Array

---

问题是求出一组数列中的第K大的数。这道题目最直白的方法是对数列进行降序排序，然后返回array[k-1]的数。这样的复杂度是O(nlogn)的，如果说这样的求第k个数被反复调用的话，我觉得排一遍序是一个合适的方法;如果是单独求解的话，nlogn的复杂度还是太高了，我们得降低复杂度。

这道题目是有O(n)的解法的，利用快排中的划分函数。划分函数的功能是将一个数列根据一个数重新布局，使得该数左边的数都小于它，右边的数都大于它。

利用这个划分的思想，我们可以这样做，将任取一个数对其进行划分，设划分后该数左边的数列为Sa，右边的数列为Sb。

如果划分后的数是第k的话，那么就返回该数；如果Sb的大小小于k的话，那么在Sa中找第k-size(Sb)大的数；如果Sb大小比k大的话，那么在Sb找继续找第k个的数。