【算法题】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;}
}

相关内容

热门资讯

梅花的诗句王安石 梅花的诗句王安石  王安石所写的一首关于梅花的诗句《梅花》是一篇经典的诗篇,影响非常的深远,如今,这...
琵琶行教学视频 琵琶行教学视频  下面是小编和大家分享的琵琶行教学视频,欢迎大家观看!  》》》》点击:琵琶行教学视...
爱国的诗句 实用爱国的诗句  爱国诗句四句诗有哪些呢?从爱国诗句四句诗中,激发我们心中的爱国热情。欢迎阅读小编整...
爱国的格言和古诗句 爱国的格言和古诗句  引导语:感时思报国,拔剑起蒿莱。我们一起来学习下面的`关于爱国的格言和古诗句,...
表达喜悦心情的诗句 表达喜悦心情的诗句  在平平淡淡的学习、工作、生活中,大家总免不了要接触或使用诗句吧,诗句具有精炼、...
经典现代诗词 1.《初恋》——日·岛崎藤村记得苹果树下初次相会,你乌黑的云发刚刚束起。一把雕梳斜插在头上,衬着脸庞...
七夕落雨诗歌 七夕落雨诗歌  在现实生活或工作学习中,许多人对一些广为流传的诗歌都不陌生吧,诗歌一般饱含丰富的想象...
感恩教师节现代诗歌 感恩教师节现代诗歌  导语:感恩教师,呕心鹿血培育我们成长。下面是感恩教师节现代诗歌,欢迎参考!  ...
余光中的诗歌《乡愁四韵》赏析 余光中的诗歌《乡愁四韵》赏析  《乡愁四韵》,台湾诗界泰斗、文化名流、知名学者——余光中先生的诗歌名...
2021喜迎建党100周年争... 在2021迎来建党100周年华诞之际,我们一定要听党的话,永远跟着党的步伐,一定要一心向党!让我们一...
教师节的小诗歌 教师节的小诗歌  在平平淡淡的日常中,大家总少不了接触一些耳熟能详的诗歌吧,诗歌具有语言高度凝练、篇...
听说爱情曾经来过爱情诗歌 听说爱情曾经来过爱情诗歌  ——人不能总是活在过去、  就用这诗、了结了我的回忆吧  如果有一天、 ...
歌颂祖国的诗歌朗诵稿 歌颂祖国的诗歌朗诵稿  在平日的学习、工作和生活里,大家都经常接触到诗歌吧,诗歌语言凝练而形象性强,...
等我一起入梦诗歌 等我一起入梦诗歌  曾记得当年的那次相遇  仿佛时光停留在了昨日  还是原来的你面若桃花  逝去的岁...
秋日行村路诗歌鉴赏答案 秋日行村路诗歌鉴赏答案  [宋]乐雷发  儿童篱落带斜阳, 豆荚姜芽社肉①香。  一路稻花谁是主? ...
落樱纷纷爱情诗歌 落樱纷纷爱情诗歌  樱花颂  樱花缤纷满天  春风拂来  一片红颜落在肩上  种上一朵爱恋的暖阳  ...
适合运动会朗诵的诗歌 适合运动会朗诵的诗歌  在生活、工作和学习中,大家都收藏过令自己印象深刻的诗歌吧,诗歌一般饱含丰富的...
生命的简短诗歌 关于生命的简短诗歌  在平时的学习、工作或生活中,大家都看到过许多经典的诗歌吧,诗歌具有精炼、集中,...
写给父亲散文诗歌 写给父亲散文诗歌  爸爸的爱像月光,总能在黑暗的时候给我们指引方向,让我们走向正确的道路,并且一步一...