力扣2208.将数组各元素总和减半需要最少次数(贪心+堆)

server/2024/9/23 18:48:59/

题目描述

给你一个正整数数组 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 个操作使数组和减少至少一半。

贪心思想

其实挺简单的 我们只要每次找到最大值减半就行,你没有听错,就是这样,但是我们找最大值可不是每次都遍历数组找最大值,拿太恶心了!!!!!我们应该建立大根堆,每次堆顶元素就是最大值

class Solution {public int halveArray(int[] array) {//因为创建堆时候默认是小根堆,我们需要更改compareTo比较方式PriorityQueue<Double> pri = new PriorityQueue<>((a, b)->b.compareTo(a));double sum=0.0;for(double x: array){sum+=x;pri.offer(x);}sum=sum/2;int count=0;//现在只要保证sum到零就是总的和减少了一半while(sum>0){double x=pri.poll()/2;pri.offer(x);count++;sum-=x;}return count;}
}


http://www.ppmy.cn/server/120924.html

相关文章

自动化生成与更新 Changelog 文件

在软件开发中&#xff0c;保持 Changelog 文件的更新是一项至关重要的任务。 Changelog 文件记录了项目的每一个重要变更&#xff0c;包括新功能、修复的问题以及任何可能破坏现有功能的变更。对于维护者、贡献者和最终用户来说&#xff0c;这都是一个宝贵的资源。然而&#x…

聊聊AUTOSAR:基于Vector MICROSAR的TC8测试开发方案

技术背景 车载以太网技术作为汽车智能化和网联化的重要组成部分&#xff0c;正逐步成为现代汽车网络架构的核心&#xff0c;已广泛应用于汽车诊断&#xff08;如OBD&#xff09;、ECU软件更新、智能座舱系统、高清摄像头环视泊车系统等多个领域。 在这个过程中&#xff0c;ET…

【Android】模糊搜索与数据处理

【Android】模糊搜索与数据处理 本篇博客主要以根据输入内容动态获取城市为例进行讲解。 获取城市 这一部分主要是根据输入的信息去动态获取城市信息 首先定义了一个名为 NetUtil 的类&#xff0c;主要用于通过 HTTP 请求获取城市信息。 public class NetUtil {private stat…

Mysql系列-索引优化

1 Explain工具介绍 使用Explain关键字可以模拟优化器执行SQL语句&#xff0c;分析查询语句或结构的性能瓶颈&#xff0c;在select语句之前增加explain关键字&#xff0c;mysql会在查询上设置一个标记&#xff0c;执行查询会返回执行计划的信息&#xff0c;而不是执行当前SQL; …

Webpack:现代前端项目的强大打包工具

在现代前端开发中&#xff0c;随着应用的复杂性不断提高&#xff0c;我们需要一种工具来管理项目的依赖、优化代码结构并打包资源文件。Webpack 就是这样一个强大的打包工具&#xff0c;它为前端开发者提供了灵活、强大且可扩展的功能。本文将介绍 Webpack 的基本概念、安装与使…

【Linux篇】常用命令及操作技巧(基础篇)

&#x1f30f;个人博客主页&#xff1a;意疏-CSDN博客 希望文章能够给到初学的你一些启发&#xff5e; 如果觉得文章对你有帮助的话&#xff0c;点赞 关注 收藏支持一下笔者吧&#xff5e; 阅读指南&#xff1a; 开篇说明帮助命令常见的七个linux操作终端实用的技巧跟文件目录…

Qt 模型视图(四):代理类QAbstractItemDelegate

文章目录 Qt 模型视图(四):代理类QAbstractItemDelegate1.基本概念1.1.使用现有代理1.2.一个简单的代理 2.提供编辑器3.向模型提交数据4.更新编辑器的几何图形5.编辑提示 Qt 模型视图(四):代理类QAbstractItemDelegate ​ 模型/视图结构是一种将数据存储和界面展示分离的编程方…

Android RecyclerView 实现 GridView ,并实现点击效果及方向位置的显示

效果图 一、引入 implementation com.github.CymChad:BaseRecyclerViewAdapterHelper:2.9.30 二、使用步骤 1.Adapter public class UnAdapter extends BaseQuickAdapter<UnBean.ResultBean, BaseViewHolder> {private int selectedPosition RecyclerView.NO_POSITIO…