链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
这道题有两种方法，一种是用大根堆来做，先把所有的数都放到大根堆里面，因为大根堆每次弹出的都是堆里面最大的数，所以弹出的第k个数，就是数组中的第k大的数。
c++代码如下：
1 class Solution { 2 public: 3 int findKthLargest(vector<int>& nums, int k) { 4 priority_queue<int> max; 5 for(auto x: nums){ 6 max.push(x); 7 } 8 int t = 0; 9 while(k--){ 10 t = max.top(); 11 max.pop(); 12 } 13 return t; 14 } 15 };
使用大根堆会使用额外的空间，所以另一种方法是快速选择法。快速选择法和快速排序差不多原理，但区别在于它不用排好序，嗯，从名字就能知道。。。在有n个数字的数组中，求第k大的数，等价于求第kk = n-k+1小的数字。比如说在数组[1, 2]中，第2大的数，就是第1 (2-2+1)小的数。
然后就是利用快排的思想啦，随机选取一个数（我一般选取中间的数），让这个数左边的数都比它小，右边的数都比它大，然后看看左边区间的数总共有多少，如果左边超过了或者刚好等于kk个数的话，那么第kk小的数肯定是在左边啦，那么就在左边的区间再递归寻找。否则，在右边的区间递归寻找。超级简单的吧^ ^
c++代码如下：
1 class Solution { 2 public: 3 vector<int> n; 4 5 int findKthLargest(vector<int>& nums, int k) { 6 k = nums.size() - k + 1; 7 return fast_select(nums, 0, nums.size() - 1, k); 8 } 9 int fast_select(vector<int>& q, int l, int r, int k){ 10 if(l >= r) return q[l]; 11 12 int i = l - 1, j = r + 1, x = q[l + r >> 1]; 13 while(i < j){ 14 do j--; while(q[j] > x); 15 do i++; while(q[i] < x); 16 if(i < j) swap(q[i], q[j]); 17 } 18 if(j - l + 1 >= k) return fast_select(q, l, j, k); 19 else return fast_select(q, j+1, r, k-(j-l+1)); 20 } 21 };
其实呢，也可以直接求第k大的数的。只要把上面的代码中，第14行的>变成<，第15行的<变成>哈哈。也就是说，我们把所有大于某数的放在左边，所有小于某数的放在右边。这样左边区间的数全部都大于右边区间的数，如果左边区间的个数大于等于k，说明第k大的数一定在左边～否则在右边。
c++代码如下：
1 class Solution { 2 public: 3 vector<int> n; 4 5 int findKthLargest(vector<int>& nums, int k) { 6 // k = nums.size() - k + 1; 7 return fast_select(nums, 0, nums.size() - 1, k); 8 } 9 int fast_select(vector<int>& q, int l, int r, int k){ 10 if(l >= r) return q[l]; 11 12 int i = l - 1, j = r + 1, x = q[l + r >> 1]; 13 while(i < j){ 14 do j--; while(q[j] < x); 15 do i++; while(q[i] > x); 16 if(i < j) swap(q[i], q[j]); 17 } 18 if(j - l + 1 >= k) return fast_select(q, l, j, k); 19 else return fast_select(q, j+1, r, k-(j-l+1)); 20 } 21 };
原文：https://www.cnblogs.com/hellosnow/p/12152733.html