题目描述 [最小的k个数]

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

解题思路

维护一个最小堆

代码

class Solution {
public:
    void maxHeap(vector<int> &nums, int i, int high){
        int left = 2*i+1, right = 2*i+2;
        int largest;
        if(left<high&&nums[left]<nums[i]) largest = left;
        else largest = i;

        if(right<high&&nums[right]<nums[largest]) largest = right;

        if(largest!=i){
            swap(nums[i], nums[largest]);
            maxHeap(nums, largest, high);
        }
    }

    void bulidHeap(vector<int> &nums){
        for(int i=nums.size()/2-1; i>=0; i--){
            maxHeap(nums, i, nums.size());
        }
    }
    void heapSort(vector<int> &nums){
        bulidHeap(nums);
        for(int i=nums.size()-1; i>0; i--){
            swap(nums[0], nums[i]);
            maxHeap(nums, 0, i);
        }
    }

    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int n=input.size();
        vector<int> res;
        if(input.size() < k || k <= 0) return res;

        vector<int> nums(input.begin(), input.begin()+k);
        heapSort(nums);

        for(int i=k;i<n;i++){
            if(input[i]<nums[0]){
                nums[0] = input[i];
                heapSort(nums);
            }
        }
        sort(nums.begin(), nums.end());
        return nums;
    }
};

二刷

嗯，自己写堆太累，笔试面试一时半会也写不好

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(input.size()<k || input.size()==0 || k==0) return res;

        for(int i=0;i<input.size();i++){
            if(res.size()<k) res.push_back(input[i]);
            else{
                make_heap(res.begin(), res.end());
                if(input[i]<res.front()){
                    pop_heap(res.begin(), res.end());
                    res.pop_back();
                    res.push_back(input[i]);
                    push_heap(res.begin(), res.end());
                }
            }
        }
        return res;
    }
};