LeetCode 2208：将数组和减半的最少操作次数（贪心算法）—— 题解

欢迎阅读 欢迎来到「将数组和减半的最少操作次数」题解之旅本文将带你从“不断减半数组元素使总和至少降低一半”这一优化问题出发深入理解贪心 优先队列大根堆的经典应用并掌握如何每次选择当前最大值进行减半以最快达到目标。在开始之前建议你先了解题目背景这是 LeetCode 2028 题给定正整数数组nums每次操作可将任意一个数减半可重复操作同一数求使数组总和至少减少一半所需的最少操作次数。明确学习目标掌握如何用大根堆动态维护当前最大值模拟贪心过程每次取出最大值减半后再放回堆中累加减少的总和直到达到目标值。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [5,19,8,1]输出3。本文将从问题转化、贪心策略设计、数据结构选择优先队列、模拟流程到代码实现层层递进。即使你对贪心和堆还不熟悉我们也会从“每次挑最大的砍半”这一直觉出发让你轻松抓住核心思想——局部最优每次减半收益最大即全局最优。现在让我们一起不断砍半数字用最少的操作让总和腰斩吧 一、题目2208. 将数组和减半的最少操作次数 - 力扣LeetCode二、做题思路1. 问题分析前置分析目标是将数组总和至少减少一半每次操作可以任选一个数将其减半。为了用最少的操作次数达到目标每次应选择当前最大的数进行减半因为减半后该数减少的绝对值最大即单次收益最大。因此问题转化为每次取出当前最大值将其减半后放回累加减少量直到总减少量达到原始总和的一半。2. 贪心策略核心决策规则用最大堆优先队列存储所有数。每次取出堆顶元素t将其减半得到t/2减少量为t/2。将t/2放回堆中累计减少量操作次数加 1。重复直到累计减少量 ≥ 原始总和的一半。3. 正确性说明简单版本因为操作的目标是让总和减少一半且每次只能减半一个数所以我们希望每次操作都能带来尽可能多的减少量。当前最大的数减半后其减少的数值最大因此选择它作为操作对象能保证单次操作对总和的贡献最大。这样用最少的操作次数就能达到目标。这是一个经典的贪心策略每次选择当前最优解最终得到全局最优解。4. 实现细节边界防护使用priority_queuedouble存储浮点数因为减半可能产生小数。先计算原始总和sum目标减少量为sum / 2.0。循环中判断累计减少量是否小于目标若小于则继续操作。注意每次弹出后推入新值堆的大小不变。5. 返回值目标映射返回操作次数count即所需的最少操作次数。三、代码class Solution { public: int halveArray(vectorint nums) { // 1. 贪心策略每次将当前最大的元素减半能使总和下降最快因此操作次数最少。 // 使用大根堆priority_queue来动态维护当前最大元素。 priority_queuedouble heap; // 大根堆存储数组元素double类型便于计算 double sum 0.0; // 原数组总和 // 2. 初始化将所有元素入堆同时计算总和 for (auto x : nums) { heap.push(x); sum x; } // 目标将总和减少到原总和的一半以下 double target sum / 2.0; // 需要减小的总数值 int count 0; // 操作次数 // 3. 循环减半当当前总和即剩余待减数值 target仍大于0时继续操作 while (target 0) { // 取出当前最大元素 double maxVal heap.top(); heap.pop(); // 将该元素减半并从 target 中减去减半的值即此次操作对总和的减少量 double half maxVal / 2.0; target - half; // 将减半后的值重新入堆等待后续可能再次被选中 heap.push(half); count; // 操作次数加1 } // 4. 返回值最少操作次数 return count; } };四、流程图五、正确性说明详细版步骤 1符号与问题建模----------------------------- | 原始数组 nums | | 总和 S | | 目标累计减少量 ≥ S/2 | ----------------------------- | v ----------------------------- | 一次操作选择值 v 的元素 | | 新值 v/2 | | 本次收益 v/2 | ----------------------------- | v ----------------------------- | 贪心策略每轮选当前最大值 y | | 符号最大值为 y任意元素为 x | | 显然 x ≤ y | -----------------------------设数组总和为S目标是将总和减少至少 S/2。每次对数值为v的元素减半产生的即时收益即总和减少量为v/2。当前数组的最大元素记为y实际操作的任意元素记为x且x ≤ y。贪心策略要求每轮必须选y使本轮收益最大。步骤 2关键性质 —— 交换论证贪心选择性质取一个最优操作序列 | v 第一操作用于 x当前最大值为 yy ≥ x | -- 若 y x → 首步已是贪心 | -- 若 y x → 找到序列中第一次操作 y 的位置 | v 将 y 的操作与 x 的操作交换 | v 比较交换前后首步收益 原首步 x/2新首步 y/2 因为 y x所以 y/2 x/2 | v 总收益严格增加操作次数不变 | v 新序列仍为最优解且首步为最大元素 | v 反复交换 ⇒ 存在最优解其第一步即贪心选择详细论证取一个操作次数最少的最优序列。假设其第一步选择元素x而当前最大值为y且x y。在该序列中定位第一次对 y 执行减半的位置若从未操作 y则在末尾补一个空操作。将这两个操作对 y 的首次操作与对 x 的首操作交换其余顺序不变。交换后第一步收益从x/2变为y/2严格增大后续操作收益总和不变因同一元素多次减半的收益与顺序无关。总收益不降操作次数相同故新序列仍为最优且首步选择了最大值。步骤 3归纳递推 —— 全局最优性初始状态原始数组剩余目标 S/2 | v 由步骤2存在最优解本轮选最大值 y | v 贪心执行y → y/2累计收益 y/2 | v 更新数组状态剩余目标 S/2 - 累计收益 | -- 若剩余目标 ≤ 0 → 终止贪心序列即为最优 | -- 若剩余目标 0 → 将当前数组视为新的子问题 | v 重复应用步骤2的性质每一步都成立 | v 最终贪心序列与某个最优解完全一致详细论证由步骤2初始状态存在一个全局最优解其第一步就是贪心选择。执行这一贪心步后数组更新问题变为“在剩余目标下继续操作”的子问题。对子问题重新应用步骤2推出在已选择前一步的基础上存在一个最优解其下一步仍会选择当前最大值。依此类推归纳假设若前 k 步贪心选择都包含在某个最优解中则第 k1 步仍可通过相同交换论证被包含在该最优解中。持续至累计收益达到目标贪心生成的操作序列与某个全局最优序列在每一步上完全相同。 闭幕 恭喜你完成了「将数组和减半的最少操作次数」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题采用贪心策略每次将当前最大的元素减半。为什么这样能让总和下降最快如果每次选最小的元素减半操作次数会变多吗你能举一个小例子验证吗代码中使用大根堆priority_queue来动态获取最大值。如果不用堆而是每次排序取最大值时间复杂度会变成多少每次操作后被减半的元素可能不再是最大值但需要重新入堆等待后续可能再次被选中。为什么必须把减半后的值重新放回堆里如果不放回会有什么问题代码中使用了double类型存储元素值因为减半可能产生小数。如果题目保证所有操作结果都是整数例如每次减半后仍为整数double是否还必要如果使用int并强制整除会有什么风险延伸挑战如果题目要求将数组和至少减少 30%而不是一半代码只需要改哪一行试试看操作次数会如何变化如果你觉得本文对你有所帮助欢迎 点赞 / 收藏 关注作者获取更多题解 留言交流你的疑问或优化思路祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨