【算法题】2208. 将数组和减半的最少操作次数
创始人
2025-05-28 01:49:34
0

题目:

给你一个正整数数组 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 <= 10^5
1 <= nums[i] <= 10^7

java代码:

class Solution {public int halveArray(int[] nums) {long sum = 0;double res = 0;double target = 0;int count = 0;PriorityQueue que = new PriorityQueue<>((o1,o2) -> Double.compare(o2, o1));for (int i = 0; i < nums.length; i++) {sum += nums[i];que.add(nums[i] * 1.0);}target = sum * 1.0 / 2;// 比较已减少的数量 与 和的一半while (res < target) {double temp = que.poll();res += temp / 2;que.add(temp / 2);count++;}return count;}
}

相关内容

热门资讯

描写柳树的诗句 描写柳树的诗句(精选100句)  柳树属于广生态幅植物,对环境的'适应性很广,喜光,喜湿,耐寒,是中...
月圆相思的诗句 月圆相思的诗句大全  身边中是有着许多的诗句,有些也是描写相思的。下面是小编为大家整理的'关于月圆相...
形容亲人离别的诗句 形容亲人离别的诗句  离恨恰如春草,更行更远还生,下面是一些表达与形容亲人离别的诗句,欢迎大家阅读!...
今我来思,雨雪霏霏 “今我来思,雨雪霏霏。”出处 出自 先秦 佚名 的《采薇》“今我来思,雨雪霏霏。”全诗《采薇》 先秦...
时光流逝的诗句 时光流逝的诗句  在平平淡淡的日常中,大家一定都接触过一些使用较为普遍的诗句吧,诗句一般饱含丰富的想...
激厉努力奋斗的诗句 激厉努力奋斗的诗句(精选70句)  在日常学习、工作和生活中,大家都看到过许多经典的诗句吧,诗句具有...
描写北方的冬天的诗句 描写北方的冬天的诗句  北方的.冬天,意味着寒冷,意味着萧条,意味着不方便。接下来小编搜集了描写北方...
描写下雨的诗句古诗 描写下雨的诗句古诗  中国最早得诗句为律诗结构,格律要求严格,比如先秦时期得诗一般每句四言律诗,见于...
使至塞上经典诗句解读 使至塞上经典诗句赏析  这两句诗充实表现了诗中有画的特征,非常讲求景物的画面感。首先,它有画一样的构...
描写日落的诗句 描写日落的诗句描写日落的诗句1  落霞与孤鹜齐飞,秋水共长天一色  夕阳无限好,只是近黄昏  大漠孤...
忆昔霍将军,连年此征讨 “忆昔霍将军,连年此征讨。”出处 出自 唐代 高适 的《登百丈峰二首》“忆昔霍将军,连年此征讨。”全...
描写棋的优美诗句 描写棋的优美诗句  棋声花院闭,幡影石坛高。  满目山川似势棋,况当秋雁正斜飞。金门若召羊玄保,赌取...
总是愁媒,欲诉谁消遣 “总是愁媒,欲诉谁消遣。”出处 出自 宋代 苏轼 的《蝶恋花·蝶懒莺慵春过半》“总是愁媒,欲诉谁消遣...
游丝冉冉花枝静,青壁迢迢白鸟... “游丝冉冉花枝静,青壁迢迢白鸟过。”出处 出自 明代 王守仁 的《春晴》“游丝冉冉花枝静,青壁迢迢白...
赞美冬天的诗句 关于赞美冬天的诗句  冬天来了,赞美冬天的诗句有很多,来了解一下吧,关于赞美冬天的诗句。下面是unj...
写桂花的诗句 写桂花的诗句  引导语:‘桂香多露裛,石响细泉回。’是写桂花的诗句,那么大家...
感慨时光流逝的诗句 有关感慨时光流逝的诗句(精选145句)  在日常生活或是工作学习中,大家肯定对各类诗句都很熟悉吧,诗...
委婉表达爱意的诗句 委婉表达爱意的诗句委婉表达爱意的诗句1  1、相知是一种宿命,心灵的交汇让我们有诉不尽的浪漫情怀;相...
“佳期旷何许 望望空伫立”的... “佳期旷何许,望望空伫立”的意思如何去约定相聚的日子,只能惆怅地望着同样遥远的月亮,什么事也做不了,...
描写儿童生活的古诗 描写儿童生活的古诗(通用14篇)  在现实生活或工作学习中,大家都接触过古诗吧,古诗准确地来说应该叫...