數組中的第k個最大元素

給定整數數組 nums 和整數 k，請返回數組中第 k 個最大的元素。
請注意，你需要找的是數組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。
你必須設計并實現時間復雜度為 O(n) 的算法解決此問題。
示例 1:
輸入: [3,2,1,5,6,4], k = 2
輸出: 5
示例 2:
輸入: [3,2,3,1,2,4,5,5,6], k = 4
輸出: 4

思路：

• sort排序
  從大到小排序后，返回第k-1個元素。
• 優先隊列
  大堆的時間復雜度是$k?lo{g}_{2}N$
  小堆的時間復雜度是$(N?K)?lo{g}_{2}K$
  當k不大時，還是與O(N)接近的。

代碼：

sort排序

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {sort(nums.begin(), nums.end(), greater<int>());return nums[k - 1];}
};

大堆

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {//大堆 k * logNpriority_queue<int> pq(nums.begin(), nums.end());while (--k){pq.pop();}return pq.top();}
};

小堆

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {//小堆 （N- K）* logNpriority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);for (int i = k; i < nums.size(); ++i){if (nums[i] > pq.top()){pq.pop();pq.push(nums[i]);}}return pq.top();}
};