题解 | 最小的K个数

#include <vector>
#include <queue>
using namespace std;

class Solution {
  public:
    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
        // 处理特殊情况：如果k为0，直接返回空向量
        if (k == 0) return vector<int>();

        int n = input.size();
        // 如果k大于等于数组长度，直接返回整个数组的副本
        if (k >= n) return input;

        // 使用最大堆（priority_queue默认是最大堆）来维护当前最小的k个数
        // 堆顶元素是当前k个数中的最大值
        priority_queue<int> heap;

        // 遍历输入数组
        for (int num : input) {
            // 如果堆的大小还小于k，直接加入当前元素
            if (heap.size() < k) {
                heap.push(num);
            } else {
                // 如果堆已满（大小为k），且当前元素比堆顶元素小
                // 说明当前元素应该被包含在最小的k个数中
                if (num < heap.top()) {
                    // 移除堆顶元素（当前k个数中的最大值）
                    heap.pop();
                    // 加入当前更小的元素
                    heap.push(num);
                }
                // 如果当前元素大于等于堆顶元素，则忽略它
            }
        }

        // 将堆中的元素提取到结果向量中
        vector<int> res;
        while (!heap.empty()) {
            // 从堆顶开始取出元素（最大堆，所以先取出的是较大的元素）
            res.push_back(heap.top());
            heap.pop();
        }

        // 返回结果向量
        // 注意：结果向量中的元素顺序是从大到小的，因为是从最大堆中依次弹出的
        // 但题目要求任意顺序皆可，所以这个顺序是可以接受的
        return res;
    }
};

最小的k个数 可以使用最大堆或快排
第k小的数 一般情况：使用快速选择算法，实现简单且平均性能好;数据流场景：使用堆方法;数值范围小：使用计数排序;对最坏情况有严格要求：使用BFPRT算法