Find K-th largest element in an array. and N is much larger than k.

Notice

You can swap elements in the array

Have you met this question in a real interview?

Yes

Example

In array[9,3,2,4,8], the3rdlargest element is4.

In array[1,2,3,4,5], the1stlargest element is5,2ndlargest element is4,3rdlargest element is3and etc.

class Solution {
public:
    /**
     * @param nums an integer unsorted array
     * @param k an integer from 1 to n
     * @return the kth largest element
     */
    int kthLargestElement2(vector<int> nums, int k) {
        // Write your code here
        priority_queue<int, vector<int>, std::greater<int> > q;
        if (nums.size() < k) {
            return 0;
        }
        for (int num : nums) {
            q.push(num);
            if (q.size() > k) {
                q.pop();
            }
        }
        return q.top();
    }
};