# Kth Largest Element in an array

Nov 03, 2017

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.

int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(),nums.end(),[](int a,int b ){ return a > b; });
return nums[k-1];
}


int findKthLargest(vector<int>& nums, int k) {
return findKthLargest(nums,0,nums.size() - 1,k-1);
}
int findKthLargest(vector<int> &nums,int first,int last,int k) {
int p = partition(nums,first,last);
if (k > p) return findKthLargest(nums,p+1,last,k);
else if (k < p) return findKthLargest(nums,first,p-1,k);
else return nums[p];
}
int partition(vector<int> &nums,int first,int last) {
if (first == last) return first;
swap(nums[first],nums[(random() % (last-first) + first)]);
int k = nums[first];
while(first < last) {
while(first < last && nums[last] <= k) last--;
nums[first] = nums[last];
while(first < last && nums[first] >= k) first++;
nums[last] = nums[first];
}
nums[first] = k;
return first;
}


int heap_size;
inline int left(int idx) {
return (idx << 1) + 1;
}
inline int right(int idx) {
return (idx << 1) + 2;
}
void max_heapify(vector<int>& nums, int idx) {
int largest = idx;
int l = left(idx), r = right(idx);
if (l < heap_size && nums[l] > nums[largest]) largest = l;
if (r < heap_size && nums[r] > nums[largest]) largest = r;
if (largest != idx) {
swap(nums[idx], nums[largest]);
max_heapify(nums, largest);
}
}
void build_max_heap(vector<int>& nums) {
heap_size = nums.size();
for (int i = (heap_size >> 1) - 1; i >= 0; i--)
max_heapify(nums, i);
}
int findKthLargest(vector<int>& nums, int k) {
build_max_heap(nums);
for (int i = 0; i < k; i++) {
swap(nums[0], nums[heap_size - 1]);
heap_size--;
max_heapify(nums, 0);
}
return nums[heap_size];
}


int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> pq(nums.begin(), nums.end());
for (int i = 0; i < k - 1; i++)
pq.pop();
return pq.top();
}

LeetCodeLeetCode