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

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

Solution1：

1
2
3
4
5
6
7
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        std::sort(nums.begin(),nums.end());
        return nums[nums.size()-k];
    }
};

思路：

直接使用sort()函数。将倒数第K的元素直接返回。
这样做的复杂度就为sort函数的复杂度。

Solution2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <vector>
#include <queue>
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        std::priority_queue<int, std::vector<int>, std::greater<int> > Q;
        for(int i = 0; i < nums.size(); i++){
            if(Q.size() < k){
                Q.push(nums[i]);
            }else if(Q.top() < nums[i]){
                Q.pop();
                Q.push(nums[i]);
            }
        }
        return Q.top();
    }
};

思路：
使用最小堆。

维护一个K大小的最小堆。
最小堆的堆顶始终为最小元素。当有比堆顶更大的时候，让更大的元素进堆，堆顶的元素出堆。这样遍历一遍后。第K大的元素就到了堆顶。直接弹出即可。