【程序员面试金典】面试题 17.14. 最小K个数-Toy模板网

这篇具有很好参考价值的文章主要介绍了【程序员面试金典】面试题 17.14. 最小K个数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

描述：设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

提示：

0 <= len(arr) <= 100000
0 <= k <= min(100000, len(arr))

解题思路

思路：最直观的想法是，排序。

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

扩展：最大堆。最小的k个数，那么就可以维持一个大小为k的最大堆，先填充k个数到最大堆中，然后再依次遍历后面的数，当当前数小于最大堆堆顶则将堆顶元素弹出来并将当前元素加入堆中，最后再把最大堆的元素逐个加入结果数组中。

class Solution 
{
public:
    vector<int> smallestK(vector<int>& arr, int k) 
    {
        //排除k为0
        if(k==0)
            return {};
        //优先队列 默认大根堆
        priority_queue<int> pq(arr.begin(),arr.begin()+k);
        //插入大根堆
        for(int i=k;i<arr.size();i++)
        {
            //如果当前元素小于堆顶元素则弹出堆顶元素再插入当前元素
            if(arr[i]<pq.top())
            {
                pq.pop();
                pq.push(arr[i]);
            }
        }
        vector<int> res;
        //将大根堆转换为vector
        while(!pq.empty())
        {
            res.push_back(pq.top());
            pq.pop();
        }
        return res;
    }
};

总结：对于C++中堆的操作方法：top获取堆顶元素，push压入元素，pop弹出元素，empty判断是否为空。将vector转换为堆使用priority_queue<int> pq(arr.begin(),arr.begin()+k)，但是将堆转换为vector不可以直接转换。文章来源地址https://www.toymoban.com/news/detail-506639.html

到了这里，关于【程序员面试金典】面试题 17.14. 最小K个数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！