【算法】堆排之LCR 159.库存管理 Ⅲ（easy）
系列专栏
目录
1、题目链接
LCR 159. 库存管理 III - 力扣（LeetCode）
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、解法
选择合适的算法：
- 最小的
cnt个数将位于数组的前cnt个位置，因此选择堆排序效率较高的排序算法。实现堆排序：
- 堆排序分为两个主要部分：构建堆和调整堆。
- 构建大堆：从最后一个非叶子节点开始，向上遍历每个节点，进行向下调整（
AdjustDown），确保每个节点都满足堆的性质（父节点的值大于子节点的值，对于大堆）。- 调整堆并排序：将堆顶元素（最大值）与堆的最后一个元素交换，然后减少堆的大小，并重新调整新的堆顶元素（使用向下调整
AdjustDown），使其满足堆的性质。重复这个过程，直到堆的大小为1，此时数组已经是有序的。
4、代码
class Solution {
public:
//向下调整
void AdjustDown(vector<int>& nums, int n, int parent)
{
//子节点必须不越界。 child < nums.size()
int child = parent * 2 + 1;
while (child < n)
{
// 确认child指向大的那个孩子
if (child + 1 < n && nums[child + 1] > nums[child])
{
++child;
}
if (nums[parent] < nums[child])
{
swap(nums[parent], nums[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void HeapSort(vector<int>& nums) {
//从叶子结点建堆
for (int i = (nums.size() - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(nums, nums.size(), i);
}
int end = nums.size() - 1;
while (end > 0)
{
swap(nums[0], nums[end]);
AdjustDown(nums, end, 0);
--end;
}
}
vector<int> inventoryManagement(vector<int>& stock, int cnt) {
HeapSort(stock);
vector<int> ret;
while(cnt--)
{
ret.push_back(stock[cnt]);
}
return ret;
}
};
💗感谢阅读！💗
原文地址：https://blog.csdn.net/m0_73726899/article/details/142604288
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！