牛客對應題目鏈接：最小的K個數_牛客題霸_牛客網 (nowcoder.com)

力扣對應題目鏈接：LCR 159. 庫存管理 III - 力扣（LeetCode）

核心考點 ： topK? 問題。

---

一、《劍指Offer》內容

---

二、分析題目

1、排序（O(NlogN)）

直對原數組從小到大排序后，取出前 k 個數即可。

• 最小堆（小根堆）：樹中每個非葉子結點都不大于其左右孩子結點的值，也就是根節點最小的堆。
• 最大堆（大根堆）：樹中每個非葉子結點大于其左右孩子結點的值，也就是根節點最大的堆。

---

三、代碼

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

如果面試時遇到的面試題有多種解法，并且每個解法都各有優缺點，那么要向面試官問清楚題目的要求，輸入的特點，從而選擇最合適的解法。