题目描述

blablabla

样例

堆法

数组模拟堆 $O(O(Nlogk) )$

yxc大佬的堆排模板就是好用，谁用谁说好。

在这道题里面，我们希望求出最小的k个值。需要注意的是应该使用 大根堆 。
当堆还未满时，每次来一个放到堆的末尾，然后push_up；
每次过来一个数据的时候，判断这个数据是否小于堆顶元素，如果小于，则替换掉堆顶元素，push_down；

可以类比在超市买东西，只能买最便宜的k样东西，但是要求只能逛超市一次。
所以购物车里面放了k件商品，如果遇到更便宜的，把当前车里最贵的扔了，把该商品放进来。

push_up操作时间复杂度$O(logk)$，push_down也是$O(logk)$，总计遍历数据一遍。
所以最终复杂度是$O(Nlogk)$

C++ 代码

class Solution {
public:
    int n;
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        n = input.size();
        vector<int> res;
        for(int i=0;i<n;i++){
            if(i<k) insert(res, input[i]);
            else{
                if(input[i]<res[0]){
                    res[0]=input[i];
                    push_down(res, k-1, 0);
                }
            }
        }
        sort(res.begin(), res.end());
        return res;
    }

    void push_down(vector<int> &a, int size, int u){
        int t=u, l=u*2+1, r=u*2+2;
        if(l<=size && a[l]>a[t]) t=l;
        if(r<=size && a[r]>a[t]) t=r;
        if(t!=u){
            swap(a[u], a[t]);
            push_down(a, size, t);
        }
    }

    void push_up(vector<int> &a, int u){
        if(!u) return;
        while((u-1)/2>=0 && a[u]>a[(u-1)/2]){
            swap(a[u], a[(u-1)/2]);
            u=(u-1)/2;
        }
    }

    void insert(vector<int> &a, int x){
        a.push_back(x);
        push_up(a, a.size()-1);
    }
};