丹阳市最新疫情_我要自学网ps视频教程免费下载_seo网站快速排名外包_长春seo排名扣费

🌟 LeetCode 2208. 将数组和减半的最少操作次数：贪心策略与大根堆的完美结合

🔍 问题描述

给定一个正整数数组 nums，每次操作可以选择任意一个元素将其减半（可对同一元素多次操作）。要求找到使数组总和至少减少一半所需的最少操作次数。

示例分析

以示例 nums = [5,19,8,1] 为例：

• 初始总和：33 → 目标减少量：16.5
• 操作路径：19→9.5→4.75、8→4
• 最终总和：14.75（减少量18.25 ≥ 16.5）
• 最少操作次数：3

---

💡 算法思路

1. 贪心策略的选择

每次选择当前数组中的最大值进行减半操作，这是最优策略的数学基础：

• 交换论证法：假设某次未选最大值而选较小值，后续操作需补偿更多次数。例如，若未减半最大值 x 而选较小值 y，后续仍需处理 x，总操作次数必然更多。
• 直观理解：最大值贡献的减少量最大（x/2），优先处理能最快逼近目标。

2. 大根堆的运用

直接遍历数组找最大值的时间复杂度为 O(n²)，会超时（如 n=1e5 时）。使用**优先队列（大根堆）**优化：

• 堆特性：取最大值 O(1)，插入 O(log n)。
• 动态维护：每次减半后重新插入堆，保持堆的有效性。

---

🛠 代码实现解析

class Solution {
public:int halveArray(vector<int>& nums) {priority_queue<double> maxHeap;  // 大根堆存储元素double sum = 0;// 初始化堆并计算总和（时间复杂度O(n)）for (auto& e : nums) {maxHeap.push(e);sum += e;}int ret = 0;double target = sum / 2;  // 需减少的总量while (sum > target) {     // 循环直到满足条件double top = maxHeap.top(); maxHeap.pop();double half = top / 2; // 减半操作sum -= half;           // 更新当前总和maxHeap.push(half);    // 重新入堆（维护堆结构）++ret;                 // 操作计数}return ret;}
};

关键代码说明：

1. 堆初始化（网页4、网页10）：

   • 遍历数组压入堆 → 自动构建大根堆。
   • 计算初始总和 sum → 用于确定目标减少量。

2. 循环处理：

   • 取堆顶：当前最大值（O(1)）。
   • 减半并更新总和：实际减少量为 top/2（原值贡献的减少量为 top - top/2）。
   • 重新入堆：保持堆结构，确保下次操作仍取最大值。

---

⏳ 复杂度分析

• 时间复杂度：O(n log n)
  • 建堆：O(n)（利用 priority_queue 的构造函数优化）。
  • 堆操作：每次取最大值和插入为 O(log n)，最多操作 n 次（极端情况所有元素多次减半）。
• 空间复杂度：O(n)
  • 堆存储所有元素（最坏情况存储 n 个元素）。

---