kth largest element in an unsorted array

sort the array and pick the kth

O(Nlog(N))

Use size k min heap

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int> ,greater<int>> pq;
        for(auto n : nums){
            pq.push(n);
            if (pq.size() > k)
                pq.pop();
        }
        return pq.top();
    }
};

We use a min heap of size k to filter through all elements and if after adding an element to heap causing the heap size to exceed k, then we pop it.

This algorithm will eventually contain the kth largest element since all elements smaller than kth largest elem will be at the internal or leaf. And any node larger than kth largest will eventually be at the top and get pop off.

Quick select

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax