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

链接：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 };