leetcode LCR 159 库存管理III

一、题目描述

二、解题思路

整体思路

可以采用快速选择排序算法来解决这个问题，即三指针区间划分的方法。本题的解题思路与leetcode 215 数组中的第K个最大元素-CSDN博客一致。

具体思路

(1)当l>=r时，表示区间内只有一个元素或者没有元素，表示排序完成，直接return；

(2)调用产生随机数的函数GetRandom来获得随机基准key。left用于记录小于key的区间的右端点，初始化为l-1。right用于记录大于key的区间的左端点，初始化为r+1。i用于遍历向量，初始化为l，使用三指针将向量划分成三个部分：

<1>如果nums[i]==key，执行i++；

<2>如果nums[i]<key，执行swap(nums[++left]，nums[i++])；

<3>如果nums[i]>key，执行swap(nums[--right]，nums[i])；

(3)此时向量被划分成[l,left]，区间长度为a，[left+1,right-1]，区间长度为b，[right,r]三个区间，分三种情况进行讨论：

<1>如果a>=k，则说明这k个元素在[l,left]区间内，执行qsort(nums,l,left,k)；

<2>如果a+b>=k，则说明这k个元素在[l,left]和[left+1,right-1]区间内，无需再排序，直接return即可；

<3>否则，则说明这k个元素还需要[right+1,r]区间内的部分元素，执行qsort(nums,right+1,r,k-a-b)即可；

三、代码实现

解法一：sort排序，取最小的K个元素

时间复杂度：T(n)=O(nlogn)

空间复杂度：S(n)=O(1) 

class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {sort(stock.begin(),stock.end());return {stock.begin(),stock.begin()+cnt};}
};

解法二：快速选择排序算法

时间复杂度：T(n)=O(n)

空间复杂度：S(n)=O(1)

class Solution {
public:vector<int> inventoryManagement(vector<int>& nums, int k) {//产生随机数种子srand(time(NULL));qsort(nums,0,nums.size()-1,k);return {nums.begin(),nums.begin()+k};}//快速选择排序算法void qsort(vector<int>& nums,int l,int r,int k){//递归出口if(l>=r) return;//1.随机产生基准int key=GetRandom(nums,l,r);//2.按基准划分成三块int left=l-1,right=r+1,i=l;while(i<right){if(nums[i]==key) i++;else if(nums[i]<key) swap(nums[++left],nums[i++]);else swap(nums[--right],nums[i]);}//3.分情况处理//[l,left],[left+1,right-1],[right,r]三个区间int a=left-l+1,b=right-left-1;if(a>=k) qsort(nums,l,left,k);else if(a+b>=k) return;else qsort(nums,right,r,k-a-b);}//产生随机数int GetRandom(vector<int>& nums,int left,int right){int r=rand();return nums[left+r%(right-left+1)];}
};