个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创分治算法(4)_快速选择_库存管理III_面试题
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌
目录
温馨提示:
1. 题目链接:
2. 题目描述:
3. 解法(快速选择)
算法思路:
代码展示:
结果分析:
温馨提示:
该问题是top k问题的一类,top k问题可以使用堆排序和快速排序解决,因为题目要求使用O(N)的时间复杂度解决该问题,所以我这里就直接使用快速排序解决,想看堆排序的宝子们可以取下面的博客查看:
数据结构之二叉树的超详细讲解(2)--(堆的概念和结构的实现,堆排序和堆排序的应用)-CSDN博客
1. 题目链接:
OJ链接 : 库存管理
2. 题目描述:
仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。
示例 1：
输入：stock = [2,5,7,4], cnt = 1 输出：[2]
示例 2：
输入：stock = [0,2,3,6], cnt = 2 输出：[0,2] 或 [2,0]
提示：
0 <= cnt <= stock.length <= 10000
0 <= stock[i] <= 10000
3. 解法(快速选择)
算法思路:
这道题跟上道"找到第k个最大数"的题很想,建议大家先去看那道题,算法思路基本上是一致的.
分治算法(3)_快速选择_数组中的第K个最大元素-CSDN博客
在快排中,当我们把数组[分成三块]之后: [l, left] [left + 1, right - 1] [right, r],我们可以通过计算每一个区间内元素的[个数],进而推断出最小的k个数在那些区间里面.
那我们可以直接去[相应的区间]继续划分数组即可.
代码展示:
class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {srand(time(NULL));qsort(stock, 0, stock.size() - 1, cnt);return {stock.begin(), stock.begin() + cnt};}void qsort(vector<int>& nums, int l, int r, int cnt){if(l >= r) return;int key = getRandom(nums, l, r);int i = l, left = l - 1, right = r + 1;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}int a = left - l + 1;int b = right - left - 1;if(a > cnt) qsort(nums, l, left, cnt);else if(a + b >= cnt) return;else qsort(nums, right, r, cnt - a - b);}int getRandom(vector<int>& nums, int left, int right){int r = rand();return nums[left + r % (right - left + 1)];}
};
结果分析:
示例分析 :
在随机选择基准的情况下，期望的时间复杂度为 O(n)。这是因为在平均情况下，基准会将数组大致分成两半，这样每次递归将处理的元素数量减少大约一半。
由于每次递归的分区工作是线性的（O(n)），整个过程在期望情况下是 O(n) 的。
