陕西旭泽建设有限公司网站,电子商务网站的整体规划,做网站购买什么,百度官方客户端个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 点击直接跳转到该题目 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述
给你一个正整数数组 nums 。每一次操作中你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。注意在后续操作中你可以对减半过的数继续执行操作
请你返回将 nums 数组和 至少 减少一半的 最少 操作数。
示例 1 输入nums [5,19,8,1] 输出3 解释初始 nums 的和为 5 19 8 1 33 。 以下是将数组和减少至少一半的一种方法 选择数字 19 并减小为 9.5 。 选择数字 9.5 并减小为 4.75 。 选择数字 8 并减小为 4 。 最终数组为 [5, 4.75, 4, 1] 和为 5 4.75 4 1 14.75 。 nums 的和减小了 33 - 14.75 18.25 减小的部分超过了初始数组和的一半18.25 33/2 16.5 。 我们需要 3 个操作实现题目要求所以返回 3 。 可以证明无法通过少于 3 个操作使数组和减少至少一半。 示例 2 输入nums [3,8,20] 输出3 解释初始 nums 的和为 3 8 20 31 。 以下是将数组和减少至少一半的一种方法 选择数字 20 并减小为 10 。 选择数字 10 并减小为 5 。 选择数字 3 并减小为 1.5 。 最终数组为 [1.5, 8, 5] 和为 1.5 8 5 14.5 。 nums 的和减小了 31 - 14.5 16.5 减小的部分超过了初始数组和的一半 16.5 31/2 15.5 。 我们需要 3 个操作实现题目要求所以返回 3 。 可以证明无法通过少于 3 个操作使数组和减少至少一半。 注意
1 nums.length 1051 nums[i] 107
2️⃣题目解析
本题不是很复杂并没有很明显的使用贪心策略只是简单的使用优先队列堆来动态地获取数组中的最大值并将其逐步减半直到元素的和不超过原始数组元素和的一半。
3️⃣解题代码
class Solution {
public:int halveArray(vectorint nums) {priority_queuedouble heap;double sum 0.0;int count 0;for(int x : nums){heap.push(x);sum x;}sum / 2;while(sum 0){double tmp heap.top() / 2.0;sum - tmp;heap.pop();count;heap.push(tmp);}return count;}
};最后就通过啦
