当前位置：首页 > news >正文

【算法】堆排之LCR 159.库存管理 Ⅲ（easy）

news 来源：原创 2024/10/2 0:55:06

系列专栏

双指针

模拟算法

分治思想

1、题目链接

2、题目介绍

3、解法

选择合适的算法：

实现堆排序：

4、代码

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;}elsebreak;}}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;}
};