leetcode 215 数组中的第K大元素

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

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4

解题思路：

先排序，取第k大元素即可用快排的思想

C++

class Solution { public: int findKthLargest(vector<int>& nums, int k) { if(nums.size()==0||k<1||k>nums.size()) return -1; return partition(nums,0,nums.size()-1,nums.size()-k); } private: int partition(vector<int> &nums,int start,int end,int k){ if(start >= end) return nums[k]; int left = start,right = end; int pivot = nums[(start+end)/2]; while(left <= right){ while(nums[left] < pivot) left++; while(nums[right] > pivot) right--; if(left <= right){ swap(nums[left++],nums[right--]); } } if(k <= right){ return partition(nums,start,right,k); } if(k >= left){ return partition(nums,left,end,k); } return nums[k]; } };

python解法

class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: nums.sort() return nums[-k]