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)];
    }
};