Given an integer array, find the top_k_largest numbers in it.

Have you met this question in a real interview?

Yes

Example

Given[3,10,1000,-99,4,100]andk=3.
Return[1000, 100, 10].

class Solution {
public:
    /*
     * @param nums an integer array
     * @param k an integer
     * @return the top k largest numbers in array
     */
    vector<int> topk(vector<int>& nums, int k) {
        // Write your code here
        int minSize = min(k, static_cast<int>(nums.size()));

        priority_queue<int, vector<int>, std::greater<int>> minHeap;
        for (int i = 0; i < minSize; ++i) {
            minHeap.push(nums[i]);
        }
        for (int i = minSize; i < nums.size(); ++i) {
            if (nums[i] <= minHeap.top()) {
                continue;
            }
            minHeap.pop();
            minHeap.push(nums[i]);
        }

        vector<int> res;
        while (!minHeap.empty()) {
            res.push_back(minHeap.top());
            minHeap.pop();
        }
        sort(res.begin(), res.end(), greater<int>());

        return res;
    }
};