👋 欢迎阅读

🔥愿旖旎· 个人主页

📘学习专栏：《算法专栏》《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. 算法策略（随机基准 + 三路划分 + 单侧递归）

核心步骤：

1. 随机选基准：key = stock[rand() % 区间长度 + l]，入口srand(time(NULL))调用一次。
2. 三路划分（升序）：left = l-1、right = r+1、i = l；stock[i] < key换到左区、stock[i] == key跳过、stock[i] > key换到右区。
3. 统计三区大小：左区（全< key）长度leftlen = left - l + 1；中区（全== key）长度midlen = right - left - 1。
4. 按 cnt 定位：
   • cnt <= leftlen→ 最小的 cnt 个都在左区，递归[l, left]，cnt 不变；
   • cnt <= leftlen + midlen→ 前 cnt 个已恰好由"左区 + 部分中区"组成，直接返回；
   • 否则 → 还差一些，递归右区[right, r]，cnt 减去leftlen + midlen。
5. 返回：截取[begin, begin + cnt)，即前 cnt 个最小元素。

📊 示例（stock = [3,2,1,4]，cnt = 2，基准key = 2）：

划分后数组为[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、[left+1, 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 = 3，key = 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 = r+1为虚拟边界；getRandom中rand() % (r-l+1) + 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, begin+3)即整个数组。由于cnt始终满足0 ≤ cnt ≤ n，begin + cnt永远不会越过end()，无需额外判断——"前 cnt 个位置"就是快速选择维护出来的答案区间。

5. 返回值（目标映射）

• 返回前 cnt 个元素组成的数组：即数组中最小的 cnt 个数（顺序不限），对应题目"返回最小的 cnt 个数"。

三.代码

class Solution { public: vector<int> inventoryManagement(vector<int>& 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(vector<int>& 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、[left+1, 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(vector<int>& 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。

难点4：leftlen/midlen的公式与区间衔接

int leftlen = left - l + 1; int midlen = right - left - 1;

left是左区最右元素下标（左区为[l, left]），故leftlen = left - l + 1；中区为[left+1, right-1]，故midlen = (right-1) - (left+1) + 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 个不完整。

祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨