LeetCode 215. Kth Largest Element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.
解析：找到数组中第K大元素。这个题目挺好的，可以有C++STL中的多个方法或者结构来实现，具体下面逐一进行分析。
解法1 nth_element
这个是STL中的内置方法，nth_element（first, nth, last, comp），应用的范围由它的第一个和第三个参数指定。第二个参数是一个指向第 n 个元素的迭代器。如果这个范围内的元素是完全有序的，nth_dement() 的执行会导致第 n 个元素被放置在适当的位置。这个范围内，在第 n 个元素之前的元素都小于第 n 个元素，而且它后面的每个元素都会比它大。算法默认用 < 运算符来生成这个结果。
因此这里可以指定降序的方式，返回第K大元素，即第k-1大的元素在第k-1位置上，具体代码如下：
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
nth_element(nums.begin(), nums.begin() + k - 1, nums.end(), greater<int>());
return nums[k - 1];
}
};
运行时间：
方法2：partial_sort
部分排序，在大量的数据M中，只对前K个保持有序，相对于对整体排序，然后再选择前K个会节省不少时间。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
partial_sort(nums.begin(), nums.begin() + k, nums.end(), greater<int>());
return nums[k-1];
}
};
另外，这个问题可以通过堆来解决，用一个小堆维持一个最大K个元素在堆中；或者维持大根堆，然后pop k-1次即为所求元素，可以通过priority_queue 和multiset这两个结构来实现。
方法3：priority_queue 小根堆
priority_queue <Type, Container, Functional>
Type为数据类型， Container为保存数据的容器，Functional为元素比较方式。
如果不写后两个参数，那么容器默认用的是vector，比较方式默认用operator<，也就是优先队列是大顶堆，队头元素最大。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> pq;//小根堆，队列首元素最小
for (int num : nums) {
pq.push(num);
if (pq.size() > k) {//队列中维持K个元素
pq.pop();
}
}
return pq.top();//遍历完成后，剩余最大的K个元素，第一个即为K中最小的元素，即第K大元素
}
};
方法4：小根堆 multiset
multiset与set的不同之处在于前者允许重复元素的出现，代码如下：
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
multiset<int> mset;
for (int num : nums) {
mset.insert(num);
if (mset.size() > k) {
mset.erase(mset.begin());
}
}
return *mset.begin();
}
};
更多详细解法可直接参考下面链接介绍。
参考：
About Author
