53. 最小的k个数

题目

输入 n 个整数，找出其中最小的 k 个数。

注意：

输出数组内元素请按从小到大顺序排序;
数据范围
1≤k≤n≤1000
样例
输入：[1,2,3,4,5,6,7,8] , k=4

输出：[1,2,3,4]

思路一：小根堆，输出前k个堆顶元素

        0
 	  1   2
 	3  4 5  6
  7 8
 当堆数组长度n为9时，则从下标为3开始往上down操作，即从9/2 - 1 == 3
 down()中对应的左孩子节点下标为2*u+1, 右孩子节点下标为2*u+2

class Solution {
    
public:
    void down(vector<int>& input, int u, int len){
    
        int t = u;
        //此处是数组的下标，限制不越界即可
        if(2*u+1 <= len && input[2*u+1] < input[t]) t = 2*u+1;
        if(2*u+2 <= len && input[2*u+2] < input[t])t = 2*u+2;
        if(t != u){
    
            swap(input[u],input[t]);
            down(input,t,len);//递归对交换的位置的元素执行down()
        }
    }

    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
    
        //进行堆排序
        int len = input.size()-1;
        
        //数组下标从0开始，如果数组长度为n，则从数组下标为n/2 -1的地方开始往上执行down()
        for(int i = input.size()/2 - 1; i>=0; i--) down(input, i, len);
        
        
        vector<int> res;
        while(k--){
    
            res.push_back(input[0]);//添加到vector中
            input[0] = input[len];//把堆中的末尾元素放到堆顶
            len--;//存储堆的数组长度减少
            down(input,0,len);//对堆顶执行down
        }
        return res;
    }
};

思路二：维护一个k个数的大根堆

C++中的大根堆是优先队列priority_queue<>

class Solution {
    
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
    
        //遍历数组，维护一个堆个数为k的大根堆,最后将大根堆放到vector中，此时序列从大到小，再反转数组即可
        priority_queue<int> heap;
        // 遍历给定的数组
        for(auto num : input){
    
            heap.push(num);
            if(heap.size() > k) heap.pop();
        }
        
        vector<int> res;
        // 把维护的大根堆中的k个数放到数组中
        while(heap.size()){
    
            res.push_back(heap.top());
            heap.pop();
        }
        // 反转数组
        reverse(res.begin(),res.end());
        return res;
    }
};