# Leecode 215. Kth Largest Element in an Array

xiaoxiao2021-02-28  5

Kth Largest Element in an Array

## Description

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.

### 代码

using namespace std; class Solution { public: int findKthLargest(vector<int>& nums, int k) { int left = 0; int right = nums.size()-1; while(1){ int pos = partition(nums,left,right); if(pos == k-1) { cout<<k-1<<endl; return nums.at(pos); } else if(pos < k-1){ left = pos+1; } else{ right = pos - 1; } } } int partition(vector<int>& nums,int left,int right){ int med = nums.at(left); int left_record = left; left = left + 1; while(left <= right){ if(nums.at(left) < med && nums.at(right) > med){ int temp = nums.at(left); nums.at(left) = nums.at(right); nums.at(right) = temp; left++; right--; } if (nums.at(left) >= med){ left ++; } if(nums.at(right) <= med){ right--; } } swap(nums[left_record], nums[right]); return right; } };