题目
解题
给定整数数组 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
方法一：优先队列
但是这种方法面试可能不让用
class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int,vector<int>,less<int>> q; for(int num:nums){ q.push(num); } while(!q.empty()){ if(--k==0){ return q.top(); } q.pop(); } return -1; } };
方法二：快速选择（降序快排）
class Solution { public: int findKthLargest(vector<int>& nums, int k) { int n=nums.size(); int l=0,r=n-1; while(true){ int idx=partition(nums,l,r); if(idx==k-1){ return nums[idx]; }else if(idx<k-1){ l=idx+1; }else{ r=idx-1; } } return -1; } int partition(vector<int>& nums,int l,int r){ int i=l,j=r; while(i<j){ while(i<j&&nums[j]<=nums[l]) j--; while(i<j&&nums[i]>=nums[l]) i++; swap(nums[i],nums[j]); } swap(nums[l],nums[i]); return i; } };
