堆解决topK问题

小根堆取的话，复杂度过高O(NlogN)，数据量过大会超时

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> ans;
        while(k>0){
            heap(arr);
            ans.push_back(arr[0]);
            arr[0]=arr.back();
            arr.pop_back();
            k--;
        }//堆排序 小根堆
        return ans;
    }

    void heap(vector<int>&arr){//arr转换成小根堆
        int start = arr.size()/2 -1;
        if(arr.size()%2==0){
            int temp = arr[start];
            arr[start] = min(arr[start],arr[2*start+1]);
            if(temp > arr[2*start+1]){
                arr[2*start+1] = temp;
            }
            start--;
        }
        while(start>-1){
            int temp = arr[start];
            arr[start] = min(min(arr[start],arr[2*start+1]),arr[2*start+2]);
            if(temp== arr[start]){
                
            }
            else if(arr[2*start+1]>arr[2*start+2]){
                arr[2*start+2] = temp;
            }else{
                arr[2*start+1] = temp;
            }
            start--;
            
        }

    }
};

利用大根堆维护前K小，每次把前K小中的数与剩下的比对，把较大的输出，维护堆，遍历结束时输出的就是最小的K个数。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int>vec(k, 0);
        if (k == 0) return vec; // 排除 0 的情况
        priority_queue<int>Q;
        for (int i = 0; i < k; ++i) Q.push(arr[i]);
        for (int i = k; i < (int)arr.size(); ++i) {
            if (Q.top() > arr[i]) {
                Q.pop();
                Q.push(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = Q.top();
            Q.pop();
        }
        return vec;
    }
};