LeetCode 数组中的第K个最大元素

题目链接：

题目大意：

　　变换一下题意就是求第 k 小。

分析1：

　　利用库函数 nth_element(a + l, a + k, a + r), 它会使 a 这个数组中区间 [l, r) 内的第 k 小的元素处在第 k 个位置上(相对位置),但是它并不保证其他元素有序！ 

代码如下(期望O(N))：

 

分析2:

　　用一个大小为 k 的大顶堆维护前 k 个元素.

代码如下(O(Nlogk))：

 

分析3:

　　利用BFPRT算法.

代码如下(最坏O(N))：