【一刷《剑指Offer》】面试题 30：最小的 k 个数

牛客对应题目链接：最小的K个数_牛客题霸_牛客网 (nowcoder.com)

力扣对应题目链接：LCR 159. 库存管理 III - 力扣（LeetCode）

核心考点 ： topK 问题。

一、《剑指Offer》内容

二、分析题目

1、排序（O(NlogN)）

直对原数组从小到大排序后，取出前 k 个数即可。

2、堆排序（O(Nlogk)）

用一个大根堆实时维护数组的前 k 小的值。首先将前 k 个数插入大根堆中，随后从第 k+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。

可以采用最大堆，这里使用 priority_queue 优先级队列进行处理（底层原理类似堆），这里的核心思路在于实现 topk。

最小堆（小根堆）：树中每个非叶子结点都不大于其左右孩子结点的值，也就是根节点最小的堆。
最大堆（大根堆）：树中每个非叶子结点大于其左右孩子结点的值，也就是根节点最大的堆。

三、代码

1、排序

//力扣
class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        sort(stock.begin(), stock.end());
        vector<int> res(cnt);
        for(int i=0; i<cnt; i++)
            res[i]=stock[i];
        return res;
    }
};

2、堆排序

//牛客
class Solution {
private:
    vector<int> res;
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param input int整型vector 
     * @param k int整型 
     * @return int整型vector
     */
    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
        int n=input.size();
        if(n<=0 || k<=0 || k>n)
            return res;
        priority_queue<int> q;    
        for(int i=0; i<n; i++)
        {
            int x=input[i];
            if(i<k)
            {
                q.push(x);
            }
            else
            {
                if(x<q.top())
                {
                    q.pop();
                    q.push(x);
                }
            }
        }
        for(int i=0; i<k; i++)
        {
            int t=q.top();
            q.pop();
            res.push_back(t);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

3、快排

//力扣
//快速选择-数组分三块-优化：随机选择基准元素 O(N)
class Solution {
public:
    int getRandom(vector<int>& stock, int left, int right)
    {
        return stock[rand()%(right-left+1)+left];
    }
    void qsort(vector<int>& stock, int l, int r, int cnt)
    {
        if(l>=r) return;
        int key=getRandom(stock, l, r);
        int i=l, left=l-1, right=r+1;
        while(i<right)
        {
            if(stock[i]<key) swap(stock[++left], stock[i++]);
            else if(stock[i]==key) i++;
            else swap(stock[--right], stock[i]);
        }
        //    a             b             c
        //[l, left] [left+1, right-1] [right, r]
        int a=left-l+1;
        int b=(right-1)-(left+1)+1;
        if(a>=cnt) qsort(stock, l, left, cnt);
        else if(a+b>=cnt) return;
        else qsort(stock, right, r, cnt-a-b);
    }
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand(time(NULL));
        int n=stock.size();
        qsort(stock, 0, n-1, cnt);
        return {stock.begin(), stock.begin()+cnt};
    }
};