Leetcode 215 - Kth Largest Element in an Array

Link to problem

Description

Given an integer array nums and an integer k, return the kth, largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

Solution

Can you solve it without sorting?

Well, yes?

Here are two solutions:

1. We could place all the element in a max heap then pop k elements to reach the kth largest element. (But we kind of heap sorted the array by this method :))
2. Thank you STL.

Implementation

1. Max heap

   class Solution {
   public:
    int findKthLargest(std::vector<int> nums, int k) {
        priority_queue<int> heap(nums.begin(), nums.end());
        int output = 0;
        for (int i = 0; i < k; i++) {
            output = heap.top();
            heap.pop();
        }
        return output;
    }
   };
   

2. STL std::nth_element

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