当前位置: 首页 > news >正文

【LeetCode 算法】Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数-Greedy

文章目录

  • Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数

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 将数组和减半的最少操作次数问题描述&#xff1a;分析代码TLE优先队列 Tag Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数 问题描述&#xff1a; 给你一个正整数数组 nums 。每一次操作中&#xff0c;你…...

Doc as Code (3):业内人士的观点

作者 | Anne-Sophie Lardet 在技术传播国际会议十周年之际&#xff0c;Fluid Topics 的认证技术传播者和功能顾问 Gaspard上台探讨了“docOps 作为实现Doc as Code的中间结构”的概念。在他的演讲中&#xff0c;观众提出了几个问题&#xff0c;我们想分享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 论文&#xff1a;https://arxiv.org/abs/2112.10752 代码&#xff1a;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”机制&#xff1a;内核函数定义 tasklet使能/ 禁止 tasklet调度 tasklet删除 tasklet tasklet软中断方式的按键驱动程序(stm32mp157)tasklet使用方法&#xff1a;button_test.cgpio_key_drv.cMakefile修改设备树文件编译测试 “tasklet”机制&#xff1a; …...

PostgreSQL构建时间

– PostgreSQL构建时间 select make_timestamp(2023,7,27,7,34,16);...

2023-将jar包上传至阿里云maven私有仓库(云效制品仓库)

一、背景介绍 如果要将平时积累的代码工具jar包&#xff0c;上传至云端&#xff0c;方便团队大家一起使用&#xff0c;一般的方式就是上传到Maven中心仓库&#xff08;但是这种方式步骤多&#xff0c;麻烦&#xff0c;而且上传之后审核时间比较长&#xff0c;还不太容易通过&a…...

嵌入式linux之OLED显示屏SPI驱动实现(SH1106,ssd1306)

周日业余时间太无聊&#xff0c;又不喜欢玩游戏&#xff0c;大家的兴趣爱好都是啥&#xff1f;我觉得敲代码也是一种兴趣爱好。正巧手边有一块儿0.96寸的OLED显示屏&#xff0c;一直在吃灰&#xff0c;何不把玩一把&#xff1f;于是说干就干&#xff0c;最后在我的imax6ul的lin…...

关于element ui 安装失败的问题解决方法、查看是否安装成功及如何引入

Vue2引入 执行npm i element-ui -S报错 原因&#xff1a;npm版本太高 报错信息&#xff1a; 解决办法&#xff1a; 使用命令&#xff1a; npm install --legacy-peer-deps element-ui --save 引入&#xff1a; 在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 与中国产业发展

文章目录 &#x1f4ac;话题&#x1f4cb;前言&#x1f3af;AI 大模型的崛起&#x1f3af;中国 AI 产业的进展与挑战&#x1f3af;AI 大模型的未来展望&#x1f9e9;补充 &#x1f4dd;最后 &#x1f4ac;话题 北京时间 7 月 13 日凌晨&#xff0c;马斯克在 Twiiter 上宣布&am…...

【CesiumJS材质】(1)圆扩散

效果示例 最佳实践&#xff1a; 其他效果&#xff1a; 要素说明&#xff1a; 代码 /** 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…...

实战-单例模式和创建生产者相结合

实际中遇到了这样一个问题&#xff1a; The producer group[xxxx] has been created before, specify another instanceName (like producer.setInstanceName) please. 发生的原因是&#xff1a;一个进程内&#xff0c;创建了多个相同topic的producer。 所以问题就转换成了如何…...

[SQL挖掘机] - 窗口函数介绍

介绍: 窗口函数也称为 OLAP 函数。OLAP 是 OnLine AnalyticalProcessing 的简称&#xff0c;意思是对数据库数据进行实时分析处理。窗口函数是一种用于执行聚合计算和排序操作的功能强大的sql函数。它们可以在查询结果集中创建一个窗口&#xff08;window&#xff09;&#xf…...

原生js实现锚点滚动顶部

简介 使用原生js API实现滚动到指定容器的顶部&#xff0c;API是scrollIntoView 使用 let eldocment.querySelector() 获取dom元素el.scrollIntoView()该元素滚动到其父元素的顶部 高级用法 scrollIntoView(Options)//option可以配置如下 options{behavior&#xff1a;smoot…...

使用mysql接口遇到点问题

game_server加入了dbstorage的代码。dbstorage实现了与mysql的交互&#xff1a;driver_mysql。其中调用了mysql相关的接口。所以game_server需要链接libmysql.lib。 从官网下载了mysql的源码&#xff1a;在用cmake构建mysql工程的时候&#xff0c;遇到了一些问题。 msyql8.0需…...

excel绘制折线图或者散点图

一、背景 假如现在通过代码处理了一批数据&#xff0c;想看数据的波动情况&#xff0c;是不是还需要写个pyhon代码&#xff0c;读取文件&#xff0c;绘制曲线&#xff0c;看起来也简单&#xff0c;但是还有更简单的方法&#xff0c;就是直接生成csv文件&#xff0c;csv文件就是…...

ChatGPT长文本对话输入方法

ChatGPT PROMPTs Splitter 是一个开源工具&#xff0c;旨在帮助你将大量上下文数据分成更小的块发送到 ChatGPT 的提示&#xff0c;并根据如何处理所有块接收到 ChatGPT&#xff08;或其他具有字符限制的语言模型&#xff09;的方法。 推荐&#xff1a;用 NSDT设计器 快速搭建可…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...