【LCR 159. 库存管理 III】

一、题目描述

二、算法原理

三、代码实现

class Solution {
public:int getrandom(int left,int right,vector<int>& stock){return stock[rand()%(right-left+1)+left];}void qsort(int l,int r,vector<int>& stock,int cnt){if(l>=r){return;}int key=getrandom(l,r,stock);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[i],stock[--right]);}int a=left-l+1,b=right-left-1,c=r-right+1;if(a>cnt){qsort(l,left,stock,cnt);}else if(a+b>=cnt){}else{qsort(right,r,stock,cnt-a-b);}}vector<int> inventoryManagement(vector<int>& stock, int cnt) {srand(time(NULL));qsort(0,stock.size()-1,stock,cnt);return {stock.begin(),stock.begin()+cnt};}
};