LCR 159. 库存管理 III

这道题虽然简单，但是可以有多种解法，适合练习各种解法。

可以用基于快速排序思想的快速选择算法：

class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {vector<int> res;int len = stock.size();quick_select(stock,0,len-1,cnt);for(int i = 0;i < cnt;i++)res.push_back(stock[i]);return res;}void quick_select(vector<int>& stock,int left,int right,int cnt){if(left <= right){int pos = partition(stock,left,right);if(pos == cnt - 1){return;}else if(pos > cnt -1){quick_select(stock,left,pos - 1,cnt);}else{quick_select(stock,pos + 1,right,cnt);}}}int partition(vector<int>& stock,int left,int right){if(left >= right)return left;int pivot = stock[left];while(left < right){while(left<right&&stock[right] >= pivot) right--;stock[left] = stock[right];while(left<right&&stock[left]<= pivot) left++;stock[right] = stock[left];}stock[left] = pivot; return left;}
};