牛客对应题目链接：最小的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
如果面试时遇到的面试题有多种解法，并且每个解法都各有优缺点，那么要向面试官问清楚题目的要求，输入的特点，从而选择最合适的解法。
