【2357. 使数组中所有元素都等于零】
来源:力扣(LeetCode)
描述:
给你一个非负整数数组 nums 。在一步操作中,你必须:
- 选出一个正整数
x,x需要小于或等于nums中 最小 的 非零 元素。 nums中的每个正整数都减去x。
返回使 nums 中所有元素都等于 0 需要的 最少 操作数。
示例 1:
输入:nums = [1,5,0,3,5]
输出:3
解释:
第一步操作:选出 x = 1 ,之后 nums = [0,4,0,2,4] 。
第二步操作:选出 x = 2 ,之后 nums = [0,2,0,0,2] 。
第三步操作:选出 x = 2 ,之后 nums = [0,0,0,0,0] 。
示例 2:
输入:nums = [0]
输出:0
解释:nums 中的每个元素都已经是 0 ,所以不需要执行任何操作。
提示:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 100
方法一:排序 + 模拟
这道题要求计算将非负整数数组 nums 中的所有元素减少到 0 的最少操作数。用 m 表示数组 nums 中的最小非零元素,则可以选择不超过 m 的正整数 x,将数组中的每个非零元素减 x。为了使操作数最少,应选择 x = m,理由如下。
- 当选择 x = m 时,经过一次操作之后,数组中的所有元素 m 都变成 0,且其余的所有非零元素都减少 m。
- 当选择 x < m 时,经过一次操作之后,数组中的所有元素 m 在减少 x 之后仍大于 0,为了使数组中的最小非零元素变成 0,至少还需要一次操作,因此至少需要两次操作使数组中的所有元素 m 都变成 0,且其余的所有非零元素都减少 m。
由于当 x < m 时使元素 m 变成 0 的操作数大于当 x = m 时使元素 m 变成 0 的操作数,且两种方案中,使元素 m 变成 0 之后,剩余的最小非零元素相同(所有非零元素都减少 m),因此只有当 x = m 时才能使操作数最少。
根据上述分析,应使用贪心策略使操作数最少,贪心策略为每次选择数组中的最小非零元素作为 x,将数组中的每个非零元素减 x。
可以根据贪心策略模拟操作过程,计算最少操作数。
首先将数组 nums 按升序排序,然后从左到右遍历排序后的数组 nums。对于每个遍历到的非零元素,该元素是数组中的最小非零元素,将该元素记为 x,将数组中的每个非零元素都减 x,将操作数加 1。遍历结束之后,即可得到最少操作数。
代码:
class Solution {
public:void subtract(vector<int>& nums, int x, int startIndex) {int length = nums.size();for (int i = startIndex; i < length; i++) {nums[i] -= x;}}int minimumOperations(vector<int>& nums) {int ans = 0;sort(nums.begin(), nums.end());int length = nums.size();for (int i = 0; i < length; i++) {if (nums[i] > 0) {subtract(nums, nums[i], i);ans++;}}return ans;}
};
执行用时:0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗:7.9 MB, 在所有 C++ 提交中击败了100.00%的用户
复杂度分析
时间复杂度:O(n2),其中 n 是数组 nums 的长度。排序需要 O(nlogn) 的时间,排序之后需要遍历数组一次,对于每个非零元素,将数组中的所有非零元素减去最小非零元素需要 O(n) 的时间,因此时间复杂度是 O(n2)。
空间复杂度:O(logn),其中 n 是数组 nums 的长度。排序需要 O(logn) 的递归调用栈空间。
方法二:哈希集合
由于每次操作都将数组中的所有非零元素减少一个相同的值,因此数组中的相等元素减少到 0 的操作数相等,数组中的不相等元素减少到 0 的操作数不相等。
又由于使用贪心策略操作时,每次操作都会将数组中的最小非零元素减少到 0,因此最少操作数等于数组中的不同非零元素的个数。
使用哈希集合存储数组中的所有非零元素,则哈希集合的大小等于数组中的不同非零元素的个数,即为最少操作数。
需要注意的是,由于目标是将数组中的所有元素减少 0,如果数组中的一个元素已经是 0 则不需要对该元素执行操作,因此只需要考虑数组中的不同非零元素的个数。
代码:
class Solution {
public:int minimumOperations(vector<int>& nums) {unordered_set<int> hashSet;for (int num : nums) {if (num > 0) {hashSet.emplace(num);}}return hashSet.size();}
};
执行用时:0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗:8.2 MB, 在所有 C++ 提交中击败了28.86%的用户
复杂度分析
时间复杂度:O(n),其中 n 是数组 nums 的长度。需要遍历数组一次,每个非零元素加入哈希集合的时间是 O(1)。
空间复杂度:O(n),其中 n 是数组 nums 的长度。哈希集合需要 O(n) 的空间。
author:LeetCode-Solution
相关文章:
【2357. 使数组中所有元素都等于零】
来源:力扣(LeetCode) 描述: 给你一个非负整数数组 nums 。在一步操作中,你必须: 选出一个正整数 x ,x 需要小于或等于 nums 中 最小 的 非零 元素。nums 中的每个正整数都减去 x。 返回使 n…...
什么品牌的游戏蓝牙耳机比较好?玩游戏延迟低的蓝牙耳机推荐
游戏耳机的出现其实最主要的作用就是让玩家能够更专注的沉浸在游戏世界内,在声音层面去享受游戏的沉浸感,游戏最重要的就是操作灵敏,需要快速通过声音来判断敌人走向,所以小编特意整理了一期玩游戏延迟低的蓝牙耳机。 一、南卡小…...
day 33 状态压缩dp
二维状态压缩dp对于解决哈密顿回路问题的状态压缩dp只能计算固定起点到其他点的总方案数或最小路径等回路计数小蓝现在在第一栋教学楼,他想要访问每栋教学楼正好一次,最终回到第一栋教学楼(即走一条哈密尔顿回路)可看做࿱…...
扬帆优配|超3600股飘绿,人民币贬值近300点!外资净卖近38亿
今天早盘,A股整体震动调整,白马蓝筹股体现较弱,上证50、沪深300指数均跌超1%。 盘面上,国防军工、造纸、数字钱银、IT设备等板块逆势活跃,酿酒、酒店餐饮、钙钛矿电池、有色等板块跌幅居前。两市半日成交4577亿&#x…...
【编程基础之Python】6、Python基础知识
【编程基础之Python】6、Python基础知识Python基础知识Python的基本要素模块语句表达式注释Python的代码格式Python基础知识 Python 是一种高级的、动态的、解释型的编程语言,具有简单易学、开发效率高、可读性强等特点,广泛应用于数据科学、Web 开发、…...
selenium基本操作
爬虫与反爬虫之间的斗争爬虫:对某个网站数据或图片感兴趣,开始抓取网站信息;网站:请求次数频繁,并且访问ip固定,user_agent也是python,开始限制访问;爬虫:通过设置user_a…...
思科设备命令讲解(超基础二)
♥️作者:小刘在C站 ♥️个人主页:小刘主页 ♥️每天分享云计算网络运维课堂笔记,努力不一定有收获,但一定会有收获加油!一起努力,共赴美好人生! ♥️夕阳下,是最美的绽放࿰…...
HTML基础(3)
HTML基础单选框、复选框、下拉框文本框< script >标签属性< script >基本使用单选框、复选框、下拉框 文本框 < script >标签属性 type属性定义script元素包含或src引用的脚本语言。属性值是MIME类型,包括text/javascript,text/ecmascript, appl…...
鸿蒙3.0 APP混合开发闪退问题笔记
APP采用cordova混合开发, 鸿蒙2.0以及安卓操作系统正常使用,但是在鸿蒙3.0中出现APP闪退,对APP进行真机调试发现,鸿蒙3.0系统对crosswork插件存在兼容问题,这些问题会导致APP页面加载失败,进而导致App闪退测…...
批量操作文件功能-课后程序(JAVA基础案例教程-黑马程序员编著-第七章-课后作业)
【实验7-1】 批量操作文件功能 任务介绍 1.任务描述 在日常工作中,经常会遇到批量操作系统文件的事情,通常情况下,只能手动重复的完成批量文件的操作,这样很是费时费力。本案例要求编写一个文件管理器,…...
Hadoop3.3.1完全分布式部署
Hadoop目录Hadoop3.3.1完全分布式部署(一)1、HDFS一、安装1、基础安装1.1、配置JDK-181.2、下载并解压hadoop安装包本地运行模式测试 eg:2、完全分布式运行模式1、概要:2、编写集群分发脚本,把1~4步安装的同步到其他服务器:2.1、创建脚本vim …...
SpringMVC中的注解
SpringMVC中的注解 文章目录SpringMVC中的注解RequestMapping注解RequestMapping中的value属性RequestMapping中的method属性派生类PathVariable注解RequestParam注解RequestMapping注解 RequestMapping中的value属性 RequestMapping:既可以标识在方法上也可以标识…...
python+Vue学生作业系统 django课程在线学习网站系统
系统分为学生,教师,管理员三个角色: 学生功能: 1.学生注册登录系统 2.学生查看个人信息,修改个人信息 3.学生查看主页综合评价,查看今日值班信息 4.学生在线申请请假信息,查看请假的审核结果和请…...
CSS 美化网页元素【快速掌握知识点】
目录 一、为什么使用CSS 二、字体样式 三、文本样式 color属性 四、排版文本段落 五、文本修饰和垂直对齐 1、文本装饰 2、垂直对齐方式 六、文本阴影 七、超链接伪类 1、语法 2、示例 3、访问时,蓝色;访问后,紫色; …...
Tableau连接openGauss实践
目录 一、摘要 二、什么是Tableau? 三、安装Tableau 四、安装ODBC驱动 1、openGauss数据库 2、连接前置条件 3、Tableau连接openGauss方式一 4、Tableau连接openGauss方式二 一、摘要 Tableau可以连接到多种数据库,包括关系型数据库࿰…...
RabbitMQ 实现延迟队列
业务场景:1.生成订单30分钟未支付,则自动取消,我们该怎么实现呢?2.生成订单60秒后,给用户发短信1 安装rabbitMqwindows安装ubuntu中安装2 添加maven依赖<!-- https://mvnrepository.com/artifact/org.springframework.boot/spr…...
Spring Bean 生命周期,好像人的一生
简单说说IoC和Bean IoC,控制反转,想必大家都知道,所谓的控制反转,就是把new对象的权利交给容器,所有的对象都被容器控制,这就叫所谓的控制反转。 控制反转 Bean,也不是什么新鲜玩意儿…...
C++算法基础课 05 —— 数据结构1_单链表/双链表/栈/单调栈/队列/单调队列/KMP
文章目录 1. 单链表(用数组模拟链表)1.1 模板1.1.1 插入操作1.1.2 删除操作1.2 习题1 —— 826.单链表2. 双链表2.1 模板2.1.1 插入操作2.1.2 删除操作2.2 习题1 —— 827.双链表3. 栈(用数组模拟栈)3.1 模板3.2 习题1 —— 828.模拟栈4. 单调栈4.1 模板4.2 习题1 —— 830.单调…...
小型水库大坝安全监测的主要对象
一、监测背景 大坝监测的目的分成两个大的方面,一方面是为了验证设计、指导施工、为科研提供必要的资料;另一方面,也可以说是更重要的方面,就是为了长期监视大坝的安全运行。因此,一个成功的监测设计者不仅要能充分领会…...
常见软件开源(alpha,beta等)版本介绍
一、开发期Alpha:是内部测试版,一般不向外部发布,会有很多Bug.一般只有测试人员使用。Beta:也是测试版,这个阶段的版本会一直加入新的功能。在Alpha版之后推出。-RC(ReleaseCandidate):最终测试版本;可能成为最终产品的…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
