215. 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.

Example 1:

Input: [3,2,1,5,6,4] and k = 2

Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4

Output: 4

**Note: **

You may assume k is always valid, 1 ≤ k ≤ array’s length.

Idea

Quick Sort

We can partition the array like quick-sort. Use a pivot to partition the array to two parts, greater than pivot and less than pivot. If there are k-1 elements greater than pivot, then we have just found the k-th largest element. If there are less than k-1 elements greater than pivot, then we can continue to partition in right part. Otherwise, we continue to partition in left part. When we found there’re k-1 elements in the left part, we have finished our work.

Priority Queue

Just add all elements in the array to a priority_queue, then pop k-1 elements. And the top element is what we want.

Solution

// Quick Sort
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int high = nums.size();
        int low = 0;
        while (low < high) {
            int i = low, j = high - 1;
            int pivot = nums[low];
            while (i <= j) {
                while (i <= j && nums[i] >= pivot) {
                    i++;
                }
                while (i <= j && nums[j] < pivot) {
                    j--;
                }
                if (i < j) {
                    swap(nums[i++], nums[j--]);
                }
            }
            swap(nums[low], nums[j]);
            if (j == k - 1) {
                return pivot;
            } else if (j < k - 1) {
                low = j + 1;
            } else {
                high = j;
            }
        }
    }
};

// Priority Queue
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq;
        
        for (auto num : nums) {
            pq.push(num);
        }
        
        while (k > 1) {
            pq.pop();
            k--;
        }
        
        return pq.top();
    }
};