【LeetCode 算法】Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数-Greedy
Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数
问题描述:
给你一个正整数数组 nums 。每一次操作中,你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。(注意,在后续操作中你可以对减半过的数继续执行操作)
请你返回将 nums 数组和 至少 减少一半的 最少 操作数。
1 < = n u m s . l e n g t h < = 1 0 5 1 < = n u m s [ i ] < = 1 0 7 1 <= nums.length <= 10^5\\ 1 <= nums[i] <= 10^7 1<=nums.length<=1051<=nums[i]<=107
分析
目标是将数组的和减少到原始数组和的一半,而且是最小的操作数。
一次操作可以选任意的元素减半,而且可以重复选择某个下标的元素。所以几乎不存在限制。
也就是说一定在经过若干次操作后,可以达到目标。
记原始数组和为 s u m sum sum,那么目标就是 h a l f = s u m / 2 half = sum/2 half=sum/2;
但是问题是要求最少的,所以细化一下目标,
- 如果最后一次的操作使得最新的数组和 s ′ = = h a l f s'==half s′==half,说明这是最后一次操作,
- 同样如果 s ′ < h a l f s'<half s′<half,也是说明最后一次操作。
- 如果 s ′ > h a l f s'>half s′>half,说明还需要进行操作。
而且为了使得能够尽快使 s ′ s' s′靠近到目标 h a l f half half,每次一定是选择当前数组中的 m a x max max,进行操作。
暴力
如果是暴力的算法,就是每次选择最大,然后减半,放回去,再找一次最大,循环往复。
每次找数组的最大值的时间复杂度 O ( N ) O(N) O(N),而且要达到目标需要操作N次,整体的时间复杂度为 O ( N 2 ) O(N^2) O(N2).
所以这个暴力的时间复杂度有TLE的风险。
优先队列
所以就需要进行加速,而唯一能选的就是优先队列。
在优先队列中的维护一个最大值或最小值的平均时间复杂度是 O ( l o g N ) O(logN) O(logN),所以整体的时间复杂度就会降低到 O ( N l o g N ) O(NlogN) O(NlogN).
同时需要注意的是数据的范围,以及精度。
代码
TLE
public int halveArray(int[] nums) {Double tot = 0.0;int n = nums.length;Double[] arr = new Double[n];for(int i =0;i<n;i++){arr[i] = nums[i]*1.0;tot+= arr[i];}Double half = tot*0.5;int ans =0;for(int i =0;i<n;i++){if(half<=0) break;int id =0;double max = arr[id];for(int j =0;j<n;j++){if(arr[j]>max){max = arr[j];id = j;}}arr[id] *= 0.5;half -= arr[id];ans++;}return ans;}
时间复杂度 O ( N 2 ) O(N^2) O(N2)
空间复杂度 O ( 1 ) O(1) O(1)
优先队列
public int halveArray(int[] nums) {PriorityQueue<Double> pq = new PriorityQueue<Double>((a,b)->{return b.compareTo(a);});Double tot = 0.0;for(int num: nums){Double t = num*1.0;tot+=t;pq.offer(t);} Double half = tot*0.5;int ans =0;while(half>0&&!pq.isEmpty()){Double t = pq.poll();t *=0.5;half -= t;ans++;pq.offer(t);}return ans;}
时间复杂度 O ( N l o g N ) O(NlogN) O(NlogN)
空间复杂度 O ( N ) O(N) O(N)
Tag
Array
Greedy
Heap
相关文章:
【LeetCode 算法】Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数-Greedy
文章目录 Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数问题描述:分析代码TLE优先队列 Tag Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数 问题描述: 给你一个正整数数组 nums 。每一次操作中,你…...
Doc as Code (3):业内人士的观点
作者 | Anne-Sophie Lardet 在技术传播国际会议十周年之际,Fluid Topics 的认证技术传播者和功能顾问 Gaspard上台探讨了“docOps 作为实现Doc as Code的中间结构”的概念。在他的演讲中,观众提出了几个问题,我们想分享Gaspard的见解&#x…...
【Kafka】消息队列Kafka基础
目录 消息队列简介消息队列的应用场景异步处理系统解耦流量削峰日志处理 消息队列的两种模式点对点模式发布订阅模式 Kafka简介及应用场景Kafka比较其他MQ的优势Kafka目录结构搭建Kafka集群编写Kafka一键启动/关闭脚本 Kafka基础操作创建topic生产消息到Kafka从Kafka消费消息使…...
Java的第十五篇文章——网络编程(后期再学一遍)
目录 学习目的 1. 对象的序列化 1.1 ObjectOutputStream 对象的序列化 1.2 ObjectInputStream 对象的反序列化 2. 软件结构 2.1 网络通信协议 2.1.1 TCP/IP协议参考模型 2.1.2 TCP与UDP协议 2.2 网络编程三要素 2.3 端口号 3. InetAddress类 4. Socket 5. TCP网络…...
【深度学习】High-Resolution Image Synthesis with Latent Diffusion Models,论文
13 Apr 2022 论文:https://arxiv.org/abs/2112.10752 代码:https://github.com/CompVis/latent-diffusion 文章目录 PS基本概念运作原理 AbstractIntroductionRelated WorkMethodPerceptual Image CompressionLatent Diffusion Models Conditioning Mec…...
前端学习——Vue (Day6)
路由进阶 路由的封装抽离 //main.jsimport Vue from vue import App from ./App.vue import router from ./router/index// 路由的使用步骤 5 2 // 5个基础步骤 // 1. 下载 v3.6.5 // 2. 引入 // 3. 安装注册 Vue.use(Vue插件) // 4. 创建路由对象 // 5. 注入到new Vue中&…...
STM32MP157驱动开发——按键驱动(tasklet)
文章目录 “tasklet”机制:内核函数定义 tasklet使能/ 禁止 tasklet调度 tasklet删除 tasklet tasklet软中断方式的按键驱动程序(stm32mp157)tasklet使用方法:button_test.cgpio_key_drv.cMakefile修改设备树文件编译测试 “tasklet”机制: …...
PostgreSQL构建时间
– PostgreSQL构建时间 select make_timestamp(2023,7,27,7,34,16);...
2023-将jar包上传至阿里云maven私有仓库(云效制品仓库)
一、背景介绍 如果要将平时积累的代码工具jar包,上传至云端,方便团队大家一起使用,一般的方式就是上传到Maven中心仓库(但是这种方式步骤多,麻烦,而且上传之后审核时间比较长,还不太容易通过&a…...
嵌入式linux之OLED显示屏SPI驱动实现(SH1106,ssd1306)
周日业余时间太无聊,又不喜欢玩游戏,大家的兴趣爱好都是啥?我觉得敲代码也是一种兴趣爱好。正巧手边有一块儿0.96寸的OLED显示屏,一直在吃灰,何不把玩一把?于是说干就干,最后在我的imax6ul的lin…...
关于element ui 安装失败的问题解决方法、查看是否安装成功及如何引入
Vue2引入 执行npm i element-ui -S报错 原因:npm版本太高 报错信息: 解决办法: 使用命令: npm install --legacy-peer-deps element-ui --save 引入: 在main.js文件中引入 //引入Vue import Vue from vue; //引入…...
Selenium多浏览器处理
Python 版本 #导入依赖 import os from selenium import webdriverdef test_browser():#使用os模块的getenv方法来获取声明环境变量browserbrowser os.getenv("browser").lower()#判断browser的值if browser "headless":driver webdriver.PhantomJS()e…...
浅谈 AI 大模型的崛起与未来展望:马斯克的 xAI 与中国产业发展
文章目录 💬话题📋前言🎯AI 大模型的崛起🎯中国 AI 产业的进展与挑战🎯AI 大模型的未来展望🧩补充 📝最后 💬话题 北京时间 7 月 13 日凌晨,马斯克在 Twiiter 上宣布&am…...
【CesiumJS材质】(1)圆扩散
效果示例 最佳实践: 其他效果: 要素说明: 代码 /** Date: 2023-07-21 15:15:32* LastEditors: ReBeX 420659880qq.com* LastEditTime: 2023-07-27 11:13:17* FilePath: \cesium-tyro-blog\src\utils\Material\EllipsoidFadeMaterialP…...
实战-单例模式和创建生产者相结合
实际中遇到了这样一个问题: The producer group[xxxx] has been created before, specify another instanceName (like producer.setInstanceName) please. 发生的原因是:一个进程内,创建了多个相同topic的producer。 所以问题就转换成了如何…...
[SQL挖掘机] - 窗口函数介绍
介绍: 窗口函数也称为 OLAP 函数。OLAP 是 OnLine AnalyticalProcessing 的简称,意思是对数据库数据进行实时分析处理。窗口函数是一种用于执行聚合计算和排序操作的功能强大的sql函数。它们可以在查询结果集中创建一个窗口(window)…...
原生js实现锚点滚动顶部
简介 使用原生js API实现滚动到指定容器的顶部,API是scrollIntoView 使用 let eldocment.querySelector() 获取dom元素el.scrollIntoView()该元素滚动到其父元素的顶部 高级用法 scrollIntoView(Options)//option可以配置如下 options{behavior:smoot…...
使用mysql接口遇到点问题
game_server加入了dbstorage的代码。dbstorage实现了与mysql的交互:driver_mysql。其中调用了mysql相关的接口。所以game_server需要链接libmysql.lib。 从官网下载了mysql的源码:在用cmake构建mysql工程的时候,遇到了一些问题。 msyql8.0需…...
excel绘制折线图或者散点图
一、背景 假如现在通过代码处理了一批数据,想看数据的波动情况,是不是还需要写个pyhon代码,读取文件,绘制曲线,看起来也简单,但是还有更简单的方法,就是直接生成csv文件,csv文件就是…...
ChatGPT长文本对话输入方法
ChatGPT PROMPTs Splitter 是一个开源工具,旨在帮助你将大量上下文数据分成更小的块发送到 ChatGPT 的提示,并根据如何处理所有块接收到 ChatGPT(或其他具有字符限制的语言模型)的方法。 推荐:用 NSDT设计器 快速搭建可…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
怎么让Comfyui导出的图像不包含工作流信息,
为了数据安全,让Comfyui导出的图像不包含工作流信息,导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo(推荐) 在 save_images 方法中,删除或注释掉所有与 metadata …...
BLEU评分:机器翻译质量评估的黄金标准
BLEU评分:机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域,衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标,自2002年由IBM的Kishore Papineni等人提出以来,…...
