本文主要是介绍【一刷《剑指Offer》】面试题 30：最小的 k 个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
牛客对应题目链接：最小的K个数_牛客题霸_牛客网 (nowcoder.com)
力扣对应题目链接：LCR 159. 库存管理 III - 力扣（LeetCode）
核心考点 ： topK 问题。
一、《剑指Offer》内容
二、分析题目
1、排序（O(NlogN)）
直对原数组从小到大排序后，取出前 k 个数即可。
2、堆排序（O(Nlogk)）
用一个大根堆实时维护数组的前 k 小的值。首先将前 k 个数插入大根堆中，随后从第 k+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。
可以采用最大堆，这里使用 priority_queue 优先级队列进行处理（底层原理类似堆），这里的核心思路在于实现 topk。
- 最小堆（小根堆）：树中每个非叶子结点都不大于其左右孩子结点的值，也就是根节点最小的堆。
- 最大堆（大根堆）：树中每个非叶子结点大于其左右孩子结点的值，也就是根节点最大的堆。
三、代码
1、排序
//力扣
class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {sort(stock.begin(), stock.end());vector<int> res(cnt);for(int i=0; i<cnt; i++)res[i]=stock[i];return res;}
};2、堆排序
//牛客
class Solution {
private:vector<int> res;
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param input int整型vector * @param k int整型 * @return int整型vector*/vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {int n=input.size();if(n<=0 || k<=0 || k>n)return res;priority_queue<int> q; for(int i=0; i<n; i++){int x=input[i];if(i<k){q.push(x);}else{if(x<q.top()){q.pop();q.push(x);}}}for(int i=0; i<k; i++){int t=q.top();q.pop();res.push_back(t);}reverse(res.begin(), res.end());return res;}
};3、 快排
//力扣
//快速选择-数组分三块-优化：随机选择基准元素 O(N)
class Solution {
public:int getRandom(vector<int>& stock, int left, int right){return stock[rand()%(right-left+1)+left];}void qsort(vector<int>& stock, int l, int r, int cnt){if(l>=r) return;int key=getRandom(stock, l, r);int i=l, left=l-1, right=r+1;while(i<right){if(stock[i]<key) swap(stock[++left], stock[i++]);else if(stock[i]==key) i++;else swap(stock[--right], stock[i]);}// a b c//[l, left] [left+1, right-1] [right, r]int a=left-l+1;int b=(right-1)-(left+1)+1;if(a>=cnt) qsort(stock, l, left, cnt);else if(a+b>=cnt) return;else qsort(stock, right, r, cnt-a-b);}vector<int> inventoryManagement(vector<int>& stock, int cnt) {srand(time(NULL));int n=stock.size();qsort(stock, 0, n-1, cnt);return {stock.begin(), stock.begin()+cnt};}
};四、tips
如果面试时遇到的面试题有多种解法，并且每个解法都各有优缺点，那么要向面试官问清楚题目的要求，输入的特点，从而选择最合适的解法。
这篇关于【一刷《剑指Offer》】面试题 30：最小的 k 个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
