Practices11|41. 缺失的第一个正数(数组)、73. 矩阵置零(矩阵)
41. 缺失的第一个正数(数组)
1.题目:
给你一个未排序的整数数组 nums
,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n)
并且只使用常数级别额外空间的解决方案。
示例 1:
输入:nums = [1,2,0] 输出:3
示例 2:
输入:nums = [3,4,-1,1] 输出:2
示例 3:
输入:nums = [7,8,9,11,12] 输出:1
提示:
1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1
2.思路:
如果本题没有额外的时空复杂度要求,那么就很容易实现:
可以将数组所有的数放入哈希表,随后从 111 开始依次枚举正整数,并判断其是否在哈希表中;
我们可以从 1开始依次枚举正整数,并遍历数组,判断其是否在数组中。
如果数组的长度为 NNN,那么第一种做法的时间复杂度为 O(N),空间复杂度为 O(N);第二种做法的时间复杂度为O(N^2),空间复杂度为 O(1)。但它们都不满足时间复杂度为 O(N) 且空间复杂度为 O(1)。
「真正」满足时间复杂度为 O(N) 且空间复杂度为 O(1)的算法是不存在的,但是我们可以退而求其次:利用给定数组中的空间来存储一些状态。也就是说,如果题目给定的数组是不可修改的,那么就不存在满足时空复杂度要求的算法;但如果我们可以修改给定的数组,那么是存在满足要求的算法的。
方法一:哈希表
第一种做法:
我们可以将数组所有的数放入哈希表,随后从 1开始依次枚举正整数,并判断其是否在哈希表中。仔细想一想,我们为什么要使用哈希表?这是因为哈希表是一个可以支持快速查找的数据结构:给定一个元素,我们可以在 O(1) 的时间查找该元素是否在哈希表中。因此,我们可以考虑将给定的数组设计成哈希表的「替代产品」。
实际上,对于一个长度为 N 的数组,其中没有出现的最小正整数只能在 [1,N+1] 中。这是因为如果 [1,N]都出现了,那么答案是 N+1,否则答案是 [1,N]中没有出现的最小正整数。这样一来,我们将所有在 [1,N] 范围内的数放入哈希表,也可以得到最终的答案。而给定的数组恰好长度为 N,有了一种将数组设计成哈希表的思路:
对数组进行遍历,对于遍历到的数 x,如果它在 [1,N]的范围内,那么就将数组中的第 x−1个位置(注意:数组下标从 0开始)打上「标记」。在遍历结束之后,如果所有的位置都被打上了标记,那么答案是 N+1,否则答案是最小的没有打上标记的位置加 1。
那么如何设计这个「标记」呢?由于数组中的数没有任何限制,因此这并不是一件容易的事情。但我们可以继续利用上面的提到的性质:由于我们只在意 [1,N]中的数,因此我们可以先对数组进行遍历,把不在 [1,N]范围内的数修改成任意一个大于 N的数(例如 N+1)。这样一来,数组中的所有数就都是正数了,因此我们就可以将「标记」表示为「负号」。算法的流程如下:
我们将数组中所有小于等于 0 的数修改为 N+1;
我们遍历数组中的每一个数 x,它可能已经被打了标记,因此原本对应的数为 ∣x∣,如果 ∣x∣∈[1,N],那么我们给数组中的第 ∣x∣−1个位置的数添加一个负号。注意如果它已经有负号,不需要重复添加;
在遍历完成之后,如果数组中的每一个数都是负数,那么答案是 N+1,否则答案是第一个正数的位置加 1。
3.代码:
class Solution {public int firstMissingPositive(int[] nums) {//将数字中小于等于0的数改为 N+1for(int i=0;i<nums.length;i++){if(nums[i]<=0){nums[i]=nums.length+1;}}//遍历数组中的每一个数,它可能已经被打了标记,因此绝对值//如果在长度范围内,那给数组中的第 ∣x∣−1个位置的数添加一个负号for(int i=0;i<nums.length;i++){int num=Math.abs(nums[i]);if(num<=nums.length){nums[num-1]=-Math.abs(nums[num-1]);}}//遍历完成后如果其中每一个数都是负数,那么答案是n+1,否则答案是第一个正数位置加1.for(int i=0;i<nums.length;i++){if(nums[i]>0){return i+1;}}return nums.length+1;}
73. 矩阵置零
1.题目:
给定一个 m x n
的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 1:
输入:matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出:[[1,0,1],[0,0,0],[1,0,1]]
示例 2:
输入:matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
提示:
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1
2.思路:
//用两个标记数组记录是否有0出现,出现了将标记数组改为true,再遍历一遍寻找标记的位置
//将原数组位置被标记的元素替换为0;
3.代码:
class Solution {public void setZeroes(int[][] matrix) {//用两个标记数组记录是否有0出现,出现了将标记数组改为true,再遍历一遍寻找标记的位置//将原数组位置被标记的元素替换为0;int m=matrix.length,n=matrix[0].length;boolean[] row=new boolean[m];boolean[] col=new boolean[n];for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(matrix[i][j]==0){row[i]=true;col[j]=true;}}}for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(row[i]||col[j]){matrix[i][j]=0;}}}}
}
相关文章:
Practices11|41. 缺失的第一个正数(数组)、73. 矩阵置零(矩阵)
41. 缺失的第一个正数(数组) 1.题目: 给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1: 输入:nums [1,2,0] 输出…...
深入完整的带你了解java对象的比较
目录 元素的比较 1.基本类型的比较 2.对象比较的问题 1.运行结果 2.疑问 3.原因 对象的比较 1.覆写基类的equals 2.基于Comparble接口类的比较 3.基于比较器比较 4.三种方式对比 元素的比较 1.基本类型的比较 在Java 中,基本类型的对象可以直接比较大…...
ubuntu20.04升级GLIBC高版本方法,解决:version `GLIBC_2.34‘ not found
检查版本 strings /lib/x86_64-linux-gnu/libc.so.6 |grep GLIBC_ 1 显示结果 GLIBC_2.2.5 GLIBC_2.2.6 GLIBC_2.3 GLIBC_2.3.2 GLIBC_2.3.3 GLIBC_2.3.4 GLIBC_2.4 GLIBC_2.5 GLIBC_2.6 GLIBC_2.7 GLIBC_2.8 GLIBC_2.9 GLIBC_2.10 GLIBC_2.11 GLIBC_2.12 GLIBC_2.13 GLIBC_2…...
日产将使用东风纯电平台?官方回应:不是日产品牌
据财联社报道,日产中国在对于“日产将使用东风纯电平台”的传闻进行回应时指出,文中提及的平台将会用于日产在华合资企业的自主品牌,而不是日产品牌本身。这一消息进一步确认了之前每经网的报道,称日产将采用东风汽车最新发布的“…...
cdh6.3.2 Flink On Yarn taskmanager任务分配倾斜问题的解决办法
业务场景: Flink On Yarn任务启动 组件版本: CDH:6.3.2 Flink:1.13.2 Hadoop:3.0.0 问题描述: 在使用FLink on Yarn调度过程中,发现taskmanager总是分配在集中的几个节点上,集群…...
改进YOLO系列:3.添加SOCA注意力机制
添加SOCA注意力机制 1. SOCA注意力机制论文2. SOCA注意力机制原理3. SOCA注意力机制的配置3.1common.py配置3.2yolo.py配置3.3yaml文件配置1. SOCA注意力机制论文 暂未找到 2. SOCA注意力机制原理 3. SOCA注意力机制的配置 3.1common.py配置 ./models/common.p…...
SpringBoot整合Mybatis Plus——条件构造器Wrapper
Mybatis Plus为我们提供了如下的一些条件构造器,我们可以利用它们实现查询条件、删除条件、更新条件的构造。 条件构造器 | MyBatis-Plus (baomidou.com) 一、通过maven坐标引入依赖(注意版本!!) <dependency>…...
while循环语句
# while循环 # 通过while循环,计算1到100的总和 num 1 sum 0 while num < 100:sum num sumnum 1 print(f"1到100的和为{sum}") #嵌套语句--实现猜1-10数字游戏 import random flagTrue numrandom.randint(1,10) while flag:guess_numint(input(&q…...
【ARM 嵌入式 编译系列 11 -- GCC __attribute__((packed))详细介绍】
文章目录 __attribute__((packed)) 介绍上篇文章:ARM 嵌入式 编译系列 10.3 – GNU elfutils 工具小结 下篇文章:ARM 嵌入式 编译系列 11.1 – GCC attribute((aligned(x)))详细介绍 attribute((packed)) 介绍 __attribute__((packed)) 是 GCC 编译器的一个特性,它可以…...
Pytorch-day06-复杂模型构建-checkpoint
1、PyTorch 复杂模型构建 1、模型截图2、模型部件实现3、模型组装 2、模型定义 2.1、Sequential 1、当模型的前向计算为简单串联各个层的计算时, Sequential 类可以通过更加简单的方式定义模型。2、可以接收一个子模块的有序字典(OrderedDict) 或者一系列子模块…...
windows电脑系统自带的画图工具如何实现自由拼图
1.首先选中你要拼接的第一张图片,右键选着编辑,会自动打开自带的画图工具 然后就是打开第一张图片,如下图所示 接着就是将画布托大,如下图所示。 然后点击选择,选择下面的空白区域,选着区域的范围要比准备拼…...
直线模组的运行注意事项
直线模组是属于高精密的传动元件,大家都知道,安装不当,直线模组就无法显示其高精度的优势,不仅如此,使用不当也会磨损直线模,针对直线模组的使用安全性事宜,我们切记严苛遵照有关的安全操作规程…...
记录每日LeetCode 2236. 判断根结点是否等于子结点之和 Java实现
题目描述: 给你一个 二叉树 的根结点 root,该二叉树由恰好 3 个结点组成:根结点、左子结点和右子结点。 如果根结点值等于两个子结点值之和,返回 true ,否则返回 false 。 初始代码: /*** Definition f…...
使用PHP生成MySQL数据字典
一个项目完成之后,按照需求,我需要给这个项目写设计文档,数据库字典。 设计文档到时好说,但是数据库字典可真的是有点吓到我了。 项目开始的比较急,最开始建数据库的时候没有用excel写数据库字典。 这几十张表的数据…...
React(7)
1.React Hooks 使用hooks理由 1. 高阶组件为了复用,导致代码层级复杂 2. 生命周期的复杂 3. 写成functional组件,无状态组件 ,因为需要状态,又改成了class,成本高 1.1 useState useState();括号里面处的是初始值;返回的是一个…...
MySQL8.0新特性之用户管理
密码插件,在8.0中替换为了 sha2模式在8.0中不支持grant直接创建用户并授权,必须先建用户后grant授权。 关于密码插件sha2带来的坑? 客户端工具,navicat 、 sqlyog工具不支持(无法连接)主从复制,MGR &…...
强推9个研究生必备的免费论文下载网站
一、文献党下载器 文献党下载器把庞大的中外文献数据库资源集成在一个平台,就是把大量的中外数据库资源整合在一个站(目前文献资源量名列前茅)。不论是中文还是外文文献,不论是哪种文献类型,不论是哪个学科领域该网站…...
解读2023年上半年财报:继续押注儿童业务的361°,有着怎样的野心?
“足球热”的风还是吹到了青少年身边,近日,济南历城二中女足问鼎2023世界中学生足球锦标赛女子组冠军,中国球队时隔16年再次获得世界中学生足球锦标赛冠军,点燃了不少足球爱好者的热情。 少儿体育热之下,与之相关的运…...
音视频 ffplay播放控制
选项说明q, ESC退出播放f全屏切换p, SPC暂停m静音切换9, 09减少音量,0增加音量a循环切换音频流v循环切换视频流t循环切换字幕流c循环切换节目w循环切换过滤器或显示模式s逐帧播放left/right向后/向前拖动10秒down/up向后/向前拖动1分钟鼠标右键单击拖动与显示宽度对…...
扁线电机定子转子工艺及自动化装备
售:扁线电机 电驱对标样件 需要请联:shbinzer (拆车邦) 新能源车电机路线大趋势,自动化装配产线需求迫切永磁同步电机是新能源车驱动电机的主要技术路线。目前新能源车上最广泛应用的类型为永磁同步电机,…...
分类预测 | MATLAB实现DRN深度残差网络多输入分类预测
分类预测 | MATLAB实现DRN深度残差网络多输入分类预测 目录 分类预测 | MATLAB实现DRN深度残差网络多输入分类预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.分类预测 | MATLAB实现DRN深度残差网络多输入分类预测 2.代码说明:MATLAB实现DRN深度残差网络…...
docker学习(十五)docker安装MongoDB
什么是MongoDB? MongoDB 是一个开源的、面向文档的 NoSQL 数据库管理系统,它以高性能、灵活的数据存储方式而闻名。与传统的关系型数据库不同,MongoDB 采用了一种称为 BSON(Binary JSON)的二进制 JSON 格式来存储数据。它是一种非…...
3.JQuery closest()的用法
closest()是一个非常好用的查找祖先对象的方法,它和parent()和parents()相比,优点是简洁直观,返回0或1个对象,避免了返回很多对象而不知道怎么处理的尴尬&…...
速通蓝桥杯嵌入式省一教程:(七)定时器输入捕获中断与PWM频率占空比测量
前文已经讲述过定时器的两个用法:基本定时中断与PWM输出。本节接着介绍第三种用法:定时器输入捕获中断。 在此之前,需要解释一下前文一直出现过的与定时器有关的概念。 定时器(TIMER):所谓定时器,其基本功能就是定时…...
深入理解python虚拟机:程序执行的载体——栈帧
栈帧(Stack Frame)是 Python 虚拟机中程序执行的载体之一,也是 Python 中的一种执行上下文。每当 Python 执行一个函数或方法时,都会创建一个栈帧来表示当前的函数调用,并将其压入一个称为调用栈(Call Stac…...
云服务器-Docker容器-系统搭建部署
一、引言 最近公司在海外上云服务器,作者自己也搞了云服务器去搭建部署系统,方便了解整体架构和系统的生命周期,排查解决问题可以从原理侧进行分析实验。虽然用的云不是同一个,但是原理都是相通的。 二、选型 作者选用的是腾讯云…...
ES 索引重命名--Reindex(一)
ES reindex脚本流程,下图为整体流程: 步骤(1):每次写入把之前的索引删除再重新创建索引,然后判断索引是否创建成功,由于创建成功返回结果是json,因此用Json Input插件去解析json获得…...
Spring之bean的生命周期
目录 1.Bean的初始化过程 1.1代码详解 1.2思考 2.Bean的单例与多例选择 2.1论证单例与多例优缺点 2.2论证初始化时间点 2.3个例演示 Spring Bean的生命周期: 一、通过XML、Java annotation(注解)以及Java Configuration(配置类),等方式…...
策略梯度方法
策略梯度方法 数学背景 给定一个标量函数 J ( θ ) J\left(\theta\right) J(θ),利用梯度上升法,使其最大化,此时的 π θ \pi_\theta πθ就是最优策略。 θ t 1 θ t α ∇ θ J ( θ t ) \theta_{t1}\theta_t\alpha \nabla_\theta…...
博客系统之单元测试
对博客系统进行单元测试 1、测试查找已存在的用户 测试名称 selectByUsernameTest01 测试源码 //查找用户,存在 Test public void selectByUsernameTest01 () { UserDao userDao new UserDao(); String ret1 userDao.selectByUsername("张三").toStr…...
【ARM v8】如何在ARM上实现x86的rdtsc()函数
博主未授权任何人或组织机构转载博主任何原创文章,感谢各位对原创的支持! 博主链接 本人就职于国际知名终端厂商,负责modem芯片研发。 在5G早期负责终端数据业务层、核心网相关的开发工作,目前牵头6G算力网络技术标准研究。 博客…...
redis--事务
redis事务 在Redis中,事务是一组原子性操作的集合,它们被一起执行,要么全部执行成功,要么全部回滚。虽然Redis的事务并不遵循传统数据库的ACID特性,但它仍然提供了一种将多个命令打包成一组执行的机制,适用…...
111. 二叉树的最小深度
111. 二叉树的最小深度 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeN…...
SpringMVC归纳与总结
前言 Spring的核心是IOC,一种依赖反转的解耦思想。MVC是一种处理Web请求的架构模式,当两者的作用结合,就形成了SpringMVC。 组成及运行原理 1. 两次映射 2. 为什么用适配器模式 过滤器与拦截器 1. 范围 静态资源与动态资源2. 生命周期…...
Python学习笔记_进阶篇(三)_django知识(二)
本章内容 Django model Model 基础配置 django默认支持sqlite,mysql, oracle,postgresql数据库。 <1> sqlite django默认使用sqlite的数据库,默认自带sqlite的数据库驱动 引擎名称:django.db.backends.sqlite3 <2>mysql …...
RISC-V 整型通用寄存器介绍
简介 RISC-V64位/32位提供了32个整型通用寄存器,编号是x0~x31,这些整型通用寄存器的宽度与架构位数一致。 浮点数寄存器与整形寄存器一样也提供了32个:f0~f31,位数与架构位数一致。 通用寄存器介绍 零寄存器 x0/zero x0寄存…...
学习Vue:【性能优化】异步组件和懒加载
在Vue.js应用开发中,性能优化是一个至关重要的主题,而异步组件和懒加载是提升性能的有效方法之一。本文将介绍什么是异步组件和懒加载,以及如何在Vue.js中应用这些技术来提升应用性能。 异步组件和懒加载 异步组件 异步组件是指在需要的时候…...
pdf格式文件下载不预览,云存储的跨域解决
需求背景 后端接口中返回的是pdf文件路径比如: pdf文件路径 (https://wangzhendongsky.oss-cn-beijing.aliyuncs.com/wzd-test.pdf) 前端适配是这样的 <ahref"https://wangzhendongsky.oss-cn-beijing.aliyuncs.com/wzd-test.pdf&…...
httplib + nlohmann::json上传数据时中文乱码解决
1、nlohmann::json 1.1 编码格式使用UTF-8 参考 nlohmann::json 中文乱码解决方案 (1)将数据先转为UTF-8格式 2、httplib 2.1 上传数据前 (1)调用httplib::Response对象的set_header()方法来设置编码格式 httplib::Response res…...
JavaScript中的设计模式之一--单例模式和模块
虽然有一种疯狂天才的感觉可能很诱人,但重新发明轮子通常不是设计软件的最佳方法。很有可能有人已经遇到了和你一样的问题,并以一种聪明的方式解决了它。这样的最佳实践在形式化后被称为设计模式。今天我们来看看它们的概念,并检查单例模式和…...
回归预测 | MATLAB实现GAM广义加性模型多输入单输出回归预测(多指标,多图)
回归预测 | MATLAB实现GAM广义加性模型多输入单输出回归预测(多指标,多图) 目录 回归预测 | MATLAB实现GAM广义加性模型多输入单输出回归预测(多指标,多图)效果一览基本介绍程序设计参考资料 效果一览 基本…...
css学习4(背景)
1、CSS中,颜色值通常以以下方式定义: 十六进制 - 如:"#ff0000"RGB - 如:"rgb(255,0,0)"颜色名称 - 如:"red" 2、background-image 属性描述了元素的背景图像. 默认情况下,背景图像进…...
二、SQL,如何实现表的创建和查询
1、新建表格(在当前数据库中新建一个表格): (1)基础语法: create table [表名]( [字段:列标签] [该列数据类型] comment [字段注释], [字段:列标签] [该列数据类型] comment [字段注释], ……,…...
大数据及软件教学与实验专业实训室建设方案
一 、系统概述 大数据及软件教学与实验大数据及软件教学与实验在现代教育中扮演重要角色,这方面的教学内容涵盖了大数据处理、数据分析、数据可视化和大数据应用等多个方面。以下是大数据及软件教学与实验的一般内容:1. 数据基础知识:教授学生…...
信创办公–基于WPS的EXCEL最佳实践系列 (公式和函数)
信创办公–基于WPS的EXCEL最佳实践系列 (公式和函数) 目录 应用背景相关知识操作步骤1、认识基本的初级函数2、相对引用,绝对引用,混合引用3、统计函数4、文本函数 应用背景 熟练掌握Excel的函数工具能让我们在日常的使用中更加方…...
【Apollo】自动驾驶感知——毫米波雷达
作者简介: 辭七七,目前大一,正在学习C/C,Java,Python等 作者主页: 七七的个人主页 文章收录专栏: 七七的闲谈 欢迎大家点赞 👍 收藏 ⭐ 加关注哦!💖…...
SpringBoot部署到腾讯云
SpringBoot部署到腾讯云 此处默认已经申请到腾讯云服务器,因为本人还没有申请域名,所以就直接使用的ip地址 XShell连接到腾讯云 主机中填写腾讯云的公网ip地址 公网ip地址在下图中找到 接下来填写服务器的用户名与密码 一般centOS用户名为rootÿ…...
Git 设置代理
Git 传输分两种协议,SSH和 http(s),设置代理也需要分两种。 http(s) 代理 Command Line 使用 命令行 模式,可以在Powershell中使用以下命令设置代理: $env:http_proxy"http://127.0.0.1:7890" $env:https_proxy&quo…...
基于Spring Boot的机场VIP客户管理系统的设计与实现(Java+spring boot+MySQL)
获取源码或者论文请私信博主 演示视频: 基于Spring Boot的机场VIP客户管理系统的设计与实现(Javaspring bootMySQL) 使用技术: 前端:html css javascript jQuery ajax thymeleaf 微信小程序 后端:Java s…...
图数据库_Neo4j学习cypher语言_使用CQL_构建明星关系图谱_导入明星数据_导入明星关系数据_创建明星关系---Neo4j图数据库工作笔记0009
首先找到明星数据 可以看到有一个sheet1,是,记录了所有的关系的数据 然后比如我们搜索一个撒贝宁,可以看到撒贝宁的数据 然后这个是构建的CQL语句 首先我们先去启动服务 neo4j console 然后我们再来看一下以前导入的,可以看到导入很简单, 就是上面有CQL 看一下节点的属性...