Clean C++ solution using priority queue


  • 0
    D

    Even though the correct solution should involve the QuickSelect algorithm because it requires O(1) space cost and O(n) runtime cost, this solution is indeed pretty cool.

    class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            if (nums.empty()) return 0;
            
            std::priority_queue<int, std::vector<int>, std::less<int>> pq_;
            for (int i = 0; i < nums.size(); ++i) pq_.push(nums[i]);
            
            // down as an index starting at 0
            if (k > 0) --k;
            
            while (k != 0) {
                pq_.pop();
                --k;
            }
            
            return pq_.top();
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.