剑指offer:最小的k个数

电玩女神 2022-02-26 19:48 191阅读 0赞

## 题目描述 ##

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

思路：

使用C++中的mutiset容器(可包含重复元素)，multiset是有序的，使用greater<T>,使multiset呈递减趋势。

*  **建堆的时候，默认是大根堆，第三个参数用greater<T>会变成小根堆；**
 *  **排序的时候，默认是从小到大，但是第三个参数用greater<T>会变成从大到小**

AC C++ Solution:

multiset:

class Solution {
    public:
        vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
            int len = input.size();
            if(len<=0 || k>len) 
                return vector<int>();
             
            //greater<T>模板
            multiset<int, greater<int> > leastNums;
            
            auto vec_it = input.begin();
            for(;vec_it!=input.end();vec_it++)
            {
                //将前k个元素插入集合
                if(leastNums.size()<k)
                    leastNums.insert(*vec_it);
                else
                {
                    //第一个元素是最大值
                    auto max_it=leastNums.begin();
                    //如果后续元素<第一个元素，删除第一个，加入当前元素
                    if(*vec_it<*max_it)
                    {
                        leastNums.erase(*max_it);
                        leastNums.insert(*vec_it);
                    }
                }
            }
            return vector<int>(leastNums.begin(),leastNums.end());
        }
    };

priority\_queue:

class Solution {
    public:
        vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
            int len = input.size();
            if(len <= 0 || k > len)
                return vector<int>();
            
            priority_queue<int> q;
            
            for(int i = 0; i < len; ++i) {
                q.push(input[i]);
                if(q.size() > k)
                    q.pop();
            }
            
            vector<int> res;
            while(!q.empty()) {
                res.push_back(q.top());
                q.pop();
            }
            
            return res;
        }
    };