159.库存管理（TOPk问题！）

思路：也是tok的问题，与上篇博客思路一样，只不过是求前k个小的元素！

基于快排分块思路的代码如下：

class Solution {public:int getkey(vector&nums,int left,int right){int r=rand();return nums[r%(right-left+1)+left];}void qsort(vector&nums,int left,int right,int k){if(left>=right ) return ;vectorret(k);int l=-1,r=right+1;int i=0;int key=getkey(nums,left,right);while(i<r){if(nums[i]key){swap(nums[--r],nums[i]);}else{i++;}}int a=l-left+1;int b=r-l-1;int c=right-r+1;if(a>=k){return qsort(nums,left,l,k);}else if(a+b>=k){return ;}else{return qsort(nums,r,right,k-a-b);}return ;}vector inventoryManagement(vector& stock, int cnt) {int n=stock.size();qsort(stock,0,n-1,cnt);return {stock.begin(),stock.begin()+cnt};}};

优先级队列代码：

class Solution {public:vector inventoryManagement(vector& stock, int cnt){vectorret(cnt);priority_queue<int,vector,greater>q;for(auto ch:stock){q.push(ch);}for(int i=0;i<cnt;i++){ret[i]=q.top();q.pop();} return ret;}};