建站技术博客,新华网官网首页,建设网站企业文化,微信公众号小程序制作流程2208. 将数组和减半的最少操作次数
提示
中等
49
相关企业
给你一个正整数数组 nums 。每一次操作中#xff0c;你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。#xff08;注意#xff0c;在后续操作中你可以对减半过的数继续执行操作#xff09;
请你返…2208. 将数组和减半的最少操作次数
提示
中等
49
相关企业
给你一个正整数数组 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 16.5 。
我们需要 3 个操作实现题目要求所以返回 3 。
可以证明无法通过少于 3 个操作使数组和减少至少一半。提示
1 nums.length 1051 nums[i] 107
class Solution {public int halveArray(int[] nums) {//定义大根堆利用compareTO来比较返回int值PriorityQueueDouble queue new PriorityQueue((o1, o2) - o2.compareTo(o1));//所有数的总和double sum 0.0;for(int num : nums){queue.add((double)num);sum num;}//减去的数double sum2 0.0;//操作次数int cnt 0;while(sum2 sum/2){double x queue.poll();sum2 x/2;queue.add(x/2);cnt;}return cnt;}
}
