个人主页:兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【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 <= 105
1 <= nums[i] <= 107
2️⃣题目解析
本题不是很复杂,并没有很明显的使用贪心策略,只是简单的使用优先队列(堆)来动态地获取数组中的最大值
,并将其逐步减半,直到元素的和不超过原始数组元素和的一半。
3️⃣解题代码
class Solution {
public:int halveArray(vector<int>& nums) {priority_queue<double> 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;}
};
最后就通过啦: