Leetcode-215Kth Largest Element

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.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

题解：

取数组中第k大的数
第一反应，哇炒鸡简单，从大到小排序之后取第k个就行了；但是这道题只是想去第k大的数，换句话说，其他数是第几大的跟我们一毛钱关系都没有；鉴于这种想法，我们想到了堆的概念。
堆（heap）：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
堆中的节点的值总是不大于其父节点的值时，称为最大堆；
堆中的节点的值总是不小于其父节点的值时，称为最小堆；
这里我们用STL的priority_queue（优先级队列）来实现堆；

#include <queue>
//优先队列头文件
#include <vector>
//vector容器头文件
priority_queue<Type, Container, Functional>
//Type为数据类型， Container为保存数据的容器，Functional为元素比较方式。

最大堆（大顶堆）：

priority_queue<int> q; 

如果不写后两个参数，那么容器默认用的是vector，比较方式默认用operator<，等价于下面：

priority_queue<int, vector<int>, less<int>>;

这两者均表示优先队列时大顶堆；
最小堆（小顶堆）：

priority_queue<int, vector<int>, greater<int>> q;

表示优先队列最小堆。

还可以用make_heaq来构建最大（最小）堆，
用法：https://www.jianshu.com/p/13a56502e217

好了，在我们了解了堆的概念及实现以后，我们回过头来看这道题；
这道题是要取第k大的数，那么我们可以把前k大的数存入最小堆中，这样，堆顶的元素就是第k大的元素了。

My Solution（C/C++完整实现）：

#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    int findKthLargest(vector<int> &nums, int k) {
        priority_queue<int, vector<int>, 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();
    }
};
int main() {
    Solution s;
    vector<int> nums;
    nums.push_back(3);
    nums.push_back(2);
    nums.push_back(1);
    nums.push_back(5);
    nums.push_back(6);
    nums.push_back(4);
    printf("%d\n", s.findKthLargest(nums, 2));
    return 0;
}

结果：

5

My Solution 1（Python）:

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        nums.sort(reverse=True)
        return nums[k-1]

My Solution 2（Python）:

import heapq
class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        H = []
        for i in nums:
            heapq.heappush(H, i)
        result = heapq.nlargest(k, H)
        return result[-1]
    

Reference:

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return heapq.nlargest(k, nums)[k-1]