最小的k个数

LeetCode-剑指 Offer 40-最小的k个数

分析

Top K问题。

实现

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if (k == 0) return {};
        priority_queue<int> pq;
        for (int i = 0; i < k; ++ i) pq.push(arr[i]);

        for (int i = k; i < arr.size(); ++ i) {
            if (arr[i] < pq.top()) {
                pq.pop();
                pq.push(arr[i]);
            }
        }

        vector<int> res;
        while (!pq.empty()) {
            res.push_back(pq.top());
            pq.pop();
        }
        return res;
    }
};