力扣-面试题 17.14. 最小K个数（C++）- 排序法+大根堆法

左手的ㄟ右手 2022-09-10 04:09 127阅读 0赞

题目链接：[https://leetcode-cn.com/problems/smallest-k-lcci/][https_leetcode-cn.com_problems_smallest-k-lcci]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_17_color_FFFFFF_t_70_g_se_x_16]  
解一：排序法

class Solution {
        
    public:
        vector<int> smallestK(vector<int>& arr, int k) {
        
            if(arr.size()==0) return vector<int>();
            
            sort(arr.begin(),arr.end());
            
            return vector<int>({
        arr.begin(),arr.begin()+k});
        }
    };

解二：大根堆

class Solution {
        
    public:
        vector<int> smallestK(vector<int>& arr, int k) {
        
            //C++中的堆（优先队列）为大根堆
            vector<int> result(k,0);//不能少(k,0)！！！因为返回的时k个元素的数
            if(k==0) return result;
    
            priority_queue<int> que;
            //目标：只在大根堆中存放k个元素，故此，从k+1个位置开始，但凡小于大根堆堆顶元素的，则需移除在放入当前元素
            for(int i=0;i<k;i++)
            que.push(arr[i]);
    
            for(int i=k;i<(int)arr.size();++i)
            if(que.top()>arr[i]){
        
                que.pop();
                que.push(arr[i]);
            }
    
            for(int i=0;i<k;i++){
        
                result[i]=que.top();
                que.pop();
            }
    
            return result;
        }
    };

[https_leetcode-cn.com_problems_smallest-k-lcci]: https://leetcode-cn.com/problems/smallest-k-lcci/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/cbd87b28d40e47eb8723b12f7375b831.png