【剑指offer】最小的k个数

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

分析：要求的的最小的k个数，那么我们可以采用最大堆

先往最大堆里面存储k个数，然后剩下的数和堆顶元素比较，小于堆顶元素则替换堆顶元素，最后堆中剩下的k个数就是符合要求的最小的k个数

时间复杂度：O(N*log K)

vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
{
    vector<int> ans;
    priority_queue<int,vector<int>,less<int> > q;//最大堆
    int n=input.size();
    if(k>n||k<=0)
        return ans;
        
    //先往堆中放入k个元素
    for(int i=0;i<k;i++)
        q.push(input[i]);

    for(int i=k;i<n;i++)
    {
        if(input[i]<q.top())//堆顶元素大于当前元素则替换
        {
            q.pop();
            q.push(input[i]);
        }
    }
    //堆中剩余的k个元素就是符合要求的数
    while(!q.empty())
    {
        ans.push_back(q.top());
        q.pop();
    }
    return ans;
}