欢迎阅读愿旖旎· 个人主页学习专栏《算法专栏》《LangChain学习》《贪心算法》 钱塘江上潮信来今日方知我是我✨当前学习内容《快速排序》一.题目LCR 159. 库存管理 III - 力扣LeetCode 欢迎来到「库存管理 II」题解之旅本文将带你从从仓库里挑出最便宜的几件商品这一直观场景出发深入理解快速选择随机基准 三路划分的巧妙运用并掌握如何按分区长度定位 cnt 且只递归一侧来在平均 O(n) 内挑出最小的 cnt 个元素。在开始之前建议你先了解题目背景这是 LCR 159 题面试题 40给定库存数组stock和数量cnt返回其中最小的 cnt 个数任意顺序均可。本质上不需要整体排序只要把最小的 cnt 个挪到数组前段即可问题转化为快速选择Quick Select。明确学习目标掌握三路划分小于 / 等于 / 大于与随机基准防退化理解leftlen与midlen的定位逻辑并熟练处理重复元素与右区 cnt 值换算等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如stock [3,2,1,4]cnt 2输出[1,2]或任意顺序的这两个数。本文将从问题转化、三路划分、cnt 定位、随机化到代码实现层层递进。即使你对快速选择还不熟悉我们也会从把小的扔左边、大的扔右边只看 cnt 落在哪一堆这一直觉出发让你轻松抓住核心思想——按 cnt 分堆落哪堆只钻哪堆。现在让我们一起随机选基准、三路划分挑出最小的 cnt 个元素吧 ​二、算法分析1. 问题分析前置分析题目要求返回stock中最小的 cnt 个数顺序任意。关键约束cnt ≤ n元素可含大量重复只要求最小的 cnt 个不要求有序。核心思路全排序 O(n log n) 把所有元素都排好但本任务只需保证前 cnt 个位置恰好是最小的 cnt 个——快速选择每次划分后只递归 cnt 所在的那一侧平均 O(n)。 例子为什么不必全排序stock [3,2,1,4]cnt 2全排序需得到[1,2,3,4]代价 O(n log n)而快速选择只需一次划分把1、2挪到前面确认小于 2 的有 1 个、等于 2 的有 1 个cnt 2正好落在前两个位置后两个元素根本不用处理——选择只做排序中必需的那一部分。2. 算法策略随机基准 三路划分 单侧递归核心步骤随机选基准key stock[rand() % 区间长度 l]入口srand(time(NULL))调用一次。三路划分升序left l-1、right r1、i lstock[i] key换到左区、stock[i] key跳过、stock[i] key换到右区。统计三区大小左区全 key长度leftlen left - l 1中区全 key长度midlen right - left - 1。按 cnt 定位cnt leftlen→ 最小的 cnt 个都在左区递归[l, left]cnt 不变cnt leftlen midlen→ 前 cnt 个已恰好由左区 部分中区组成直接返回否则 → 还差一些递归右区[right, r]cnt 减去leftlen midlen。返回截取[begin, begin cnt)即前 cnt 个最小元素。 示例stock [3,2,1,4]cnt 2基准key 2步骤istock[i]与 key2 比较操作leftright初始033 2换到右区--right 3-13①044 2换到右区--right 2-12②011 2换到左区left 0i02③122 2跳过i02结束2—i right划分完成02划分后数组为[1,2,4,3]左区[0,0] [1]leftlen 1、中区[1,1] [2]midlen 1、右区[2,3] [4,3]。cnt 2 ≤ leftlen midlen 2→直接返回前两个[1,2]✅正是最小的 2 个数。3. 正确性说明简单版本划分不变量循环每轮保持[l, left]全 key、[left1, right-1]全 key、[right, r]全 key三个分支各做一次合法转移不破坏不变量。定位正确左区有leftlen个元素都更小若cnt ≤ leftlen最小的 cnt 个必在左区若cnt落到中区leftlen cnt ≤ leftlen midlen说明前 cnt 个位置由左区全部 中区的一部分构成而中区元素全等于 key、右区全大于 key前 cnt 个必然恰好是最小的 cnt 个直接返回正确否则还需在右区补足cnt - leftlen - midlen才是右区内的需求数量。递归收敛每次递归区间严格缩小左区left r或右区right l且cnt始终合法必然终止。随机化保证期望性能随机基准使划分期望平衡总代价期望 O(n)极小概率退化为 O(n²)。 例子为什么cnt ≤ leftlen midlen时可以直接返回stock [2,2,2,1]cnt 3key 2划分后数组为[1,2,2,2]左区[0,0] [1]leftlen 1、中区[1,3] [2,2,2]midlen 3。cnt 3满足1 3 ≤ 4直接返回前 3 个[1,2,2]✅——中区全是 key任意取几个都等价所以无需再递归若继续往下排只会浪费时间。4. 实现细节边界防护初始化srand(time(NULL))在inventoryManagement入口调用一次qsort(stock, 0, n-1, cnt)。边界防护if (l r) return;递归终止区间 0/1 个元素天然就位left l-1、right r1为虚拟边界getRandom中rand() % (r-l1) l保证基准落在[l, r]返回{stock.begin(), stock.begin() cnt}cnt 0时返回空、cnt n时返回全部均安全。复杂度平均O(n)、最坏 O(n²)随机化后概率极低空间为期望 O(log n)的递归栈最坏 O(n)。关键操作swap(stock[left], stock[i])小值归左、swap(stock[--right], stock[i])大值归右、i 不动、cnt - leftlen - midlen右区需求换算、return {stock.begin(), stock.begin() cnt};截取前 cnt 个。 例子[begin, begin cnt)的截取语义stock [3,1,2]cnt 0返回[begin, begin)即空数组cnt 3返回[begin, begin3)即整个数组。由于cnt始终满足0 ≤ cnt ≤ nbegin cnt永远不会越过end()无需额外判断——前 cnt 个位置就是快速选择维护出来的答案区间。5. 返回值目标映射返回前 cnt 个元素组成的数组即数组中最小的 cnt 个数顺序不限对应题目返回最小的 cnt 个数。三.代码class Solution { public: vectorint inventoryManagement(vectorint stock, int cnt) { int n stock.size(); srand(time(NULL)); // 随机种子只需设置一次 qsort(stock, 0, n - 1, cnt); // 把最小的 cnt 个挑到数组前段 return { stock.begin(), stock.begin() cnt }; // 截取前 cnt 个 } // 快速选择让 [l, r] 的前段恰好装下最小的 cnt 个 void qsort(vectorint stock, int l, int r, int cnt) { // 1. 递归终止区间只剩 0 或 1 个元素天然就位 if (l r) { return; } // 2. 随机选基准避免有序输入退化为 O(n²) int key getRandom(stock, l, r); // 3. 三路划分升序小于 key 归左区、等于留中区、大于归右区 int i l; int left l - 1; // 左区右边界虚拟位置 int right r 1; // 右区左边界虚拟位置 while (i right) { if (stock[i] key) { swap(stock[left], stock[i]); // 小值归左游标前进 } else if (stock[i] key) { i; // 相等留在中区 } else { swap(stock[--right], stock[i]); // 大值归右游标不动换入元素未检查 } } // 4. 划分结果[l, left] 全小于 key、[left1, right-1] 全等于 key、[right, r] 全大于 key int leftlen left - l 1; // 左区元素个数 int midlen right - left - 1; // 中区元素个数 // 5. 按 cnt 落在哪一区决定去留 if (cnt leftlen) { qsort(stock, l, left, cnt); // 最小的 cnt 个都在左区 } else if (cnt leftlen midlen) { return; // 前 cnt 个已就位中区全相等无需细分 } else { qsort(stock, right, r, cnt - leftlen - midlen); // 右区换算新的需求数量 } } // 随机取 [l, r] 内的一个元素值作为基准 int getRandom(vectorint stock, int l, int r) { int p rand(); return stock[p % (r - l 1) l]; } };四、易错点分析难点1三路划分的方向必须与最小 cnt 个对应if (stock[i] key) { swap(stock[left], stock[i]); // 小于 key 放左边 } else { swap(stock[--right], stock[i]); // 大于 key 放右边 }本题求最小的 cnt 个所以数组应按升序分区 key的元素放左区。若沿用 215 题第 k 大的降序模板 key放左leftlen就变成比 key 大的个数cnt leftlen会把最大的 cnt 个当成答案结果完全相反。方向与目标语义必须严格对齐——本题与 215 是镜像问题写代码前先想清楚谁放左边。难点2 key分支中i不能前进else { swap(stock[--right], stock[i]); // 注意没有 i }--right处换到i位置的是尚未检查的元素可能小于 key、可能等于必须原地重查若写成swap(stock[--right], stock[i])换入元素会被直接跳过若它小于 key 就会滞留在右区分区错误。这与 75 / 215 题的右区换入未检查必须停留是同一条规则。难点3右区递归的cnt必须减去左区与中区qsort(stock, right, r, cnt - leftlen - midlen);右区元素全都大于 key前面已有leftlen midlen个更小或相等的元素因此在右区内还需补的个数是cnt - (leftlen midlen)。若漏减直接传cnt递归会把前面那些更小的元素重复计入导致最终前 cnt 个不完整或越界。三个分支中只有右区需要换算 cnt。难点4leftlen/midlen的公式与区间衔接int leftlen left - l 1; int midlen right - left - 1;left是左区最右元素下标左区为[l, left]故leftlen left - l 1中区为[left1, right-1]故midlen (right-1) - (left1) 1 right - left - 1。若把midlen误写成right - left就会把right处的元素也算进中区它实际属于右区cnt定位差一答案偏移。难点5返回的前 cnt 个不保证有序return { stock.begin(), stock.begin() cnt };快速选择只保证前 cnt 个位置恰好装了最小的 cnt 个元素但它们在数组内部的相对顺序是任意的如[3,1,2]取 2 个可能得到[1,3]或[1,2]。本题明确要求任意顺序均可所以正确若题目改成返回升序的前 cnt 个就必须在返回前再对前 cnt 个排序或改用完整排序否则结果不满足要求。看清是否要求有序是使用快速选择的前提。五、流程图 闭幕 恭喜你完成了「库存管理 II」问题的学习为了巩固知识并进一步拓展建议你 动手实践在 LeetCode 上提交代码尝试不同的测试用例。 深入思考本题采用三路划分 单侧递归。请问为什么定位到 cnt 所在分区后只需递归一侧与全排序的本质区别是什么cnt leftlen midlen时直接返回。请问为什么中区不用再细分用stock [2,2,2,1]、cnt 3说明。右区递归传的是cnt - leftlen - midlen。请问为什么必须减去这两个数量漏减会得到什么如果你觉得本文对你有所帮助欢迎 点赞 / 收藏 关注作者获取更多题解 留言交流你的疑问或优化思路 深入思考答案划分后三区大小已知左区有leftlen个更小的、中区有midlen个相等的。cnt落在哪一区就能确定答案所在区间其余两区不可能包含前 cnt 小故只需递归一侧全排序则要把两侧都排好代价 O(n log n)而这里期望 O(n)。 key放左区使左区元素都更小、排名更靠前与最小的 cnt 个方向一致若沿用降序 key放左leftlen变成更大的个数cnt leftlen会返回最大的 cnt 个方向整体反掉。右区元素都大于 key前 cnt 个里已占用了leftlen midlen个更小或相等的位置故右区内还需补cnt - leftlen - midlen个。漏减会把前面那些更小的元素重复计入导致前 cnt 个不完整。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨