从零学算法41
41.给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1:
输入:nums = [1,2,0]
输出:3
示例 2:
输入:nums = [3,4,-1,1]
输出:2
示例 3:
输入:nums = [7,8,9,11,12]
输出:1
- 我的想法很简单,当该数组排序并去重后,再去掉小于等于 0 的部分,最终遍历数组时,判断是否为从 1 开始连续的数,比如 [1,2,3] 那就返回最大值 + 1 即 4,若不为从 1 开始的连续的数组,比如 [1,3,4] 中,nums[0] == 1,但是 nums[1] != 2,说明缺失了 2,那就直接返回 2 即可。
-
public int firstMissingPositive(int[] nums) {// 排序Arrays.sort(nums);int i = 0;// 从大于 0 处开始遍历,相当于去除了小于等于 0 的部分while(i<nums.length && nums[i]<=0)i++;// 从 1 开始往后找看是否为 1,2,3,4...int ans = 1;while(i<nums.length){// 相当于去重while(i<nums.length - 1 && nums[i] == nums[i+1])i++;if(nums[i]!=ans)return ans;ans++;i++;}return ans;} - 上面也提到了,我们的理想数组应该为从 1 开始递增的正整数数组,即满足
nums[i] == i+1,也可以写作i == nums[i]-1,所以我们就交换数组元素使得所有能满足的数处于对应的位置。最后从头开始判断是否为理想中的数,不是就直接返回,如果都满足就返回数组长度 + 1 - 要处理的还有两个细节:1. 排除小于 1 的以及大于数组长度的数;2. 排除重复的数
- 第一点好判断,主要还是第二点,我们可能会写成如果 nums[i]!=i+1 就交换,那交换哪两个数呢?我们需要两个下标。所以上面说也可以写作
i == nums[i]-1因为a==b => nums[a] == nums[b],所以我们判断条件写成nums[i]==nums[nums[i]-1]。 - 而为什么不写作比如
nums[nums[i]]==nums[i+1]是因为我们需要判断位置的主体为 nums[i],所以写作 i==xxx 的形式,这样的写法每次交换位置都会把 nums[i] 放到它应该处于的位置,比如 [2,-1,-2] 在第一次遍历会把 nums[0] 也就是 2 换到应该处于的位置,即下标为 1 的位置得到 [-1,2,-2],然后继续判断 nums[0] 是否为我们想要的数… -
public int firstMissingPositive(int[] nums) {int n = nums.length;for(int i = 0;i<n;i++){// 首先数在理想数组范围// 其次如果 nums[i] 上面的数如果不是 i+1 就把它换到正确的位置,继续判断换过来的数// 直到 num[i] = i + 1 就结束这一轮循环while((nums[i]>0 && nums[i] <= n) && nums[i]!=nums[nums[i]-1]){swap(nums,i,nums[i]-1);}}for(int i = 0;i<n;i++){if(nums[i]!=i+1)return i+1;}return n+1;}public void swap(int[] nums,int i,int j){int temp = nums[i];nums[i]=nums[j];nums[j]=temp;}
相关文章:
从零学算法41
41.给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1: 输入:nums [1,2,0] 输出:3 示例 2: 输入:nums […...
FPGA高端项目:FPGA基于GS2971的SDI视频接收+OSD动态字符叠加,提供1套工程源码和技术支持
目录 1、前言免责声明 2、相关方案推荐本博已有的 SDI 编解码方案本方案的SDI接收转HDMI输出应用本方案的SDI接收图像缩放应用本方案的SDI接收纯verilog图像缩放纯verilog多路视频拼接应用本方案的SDI接收HLS图像缩放HLS多路视频拼接应用本方案的SDI接收HLS多路视频融合叠加应用…...
UML-类图详解
UML中基本概念说明 UML类图中关系连接线说明 UML类图说明 号表示public、-表示表示private、#表示protected UML类关系详解 泛化(Generalization)关系 简单的讲就是类之间的继承关系。在UML中,泛化关系用空心三角形实线来表示&…...
Python 快速获取PDF文件的页数
有时在处理或打印一个PDF文档之前,你可能需要先知道该文档包含多少页。虽然我们可以使用Adobe Acrobat这样的工具来查看页数,但对于程序员来说,编写脚本来完成这项工作会更加高效。本文就介绍一个使用Python快速获取PDF文件页数的办法。 安装…...
uniapp开发小程序使用x-www-form-urlencoded; charset=UTF-8 编码格式请求案例
使用x-www-form-urlencoded,header要放在前面,第一行位置。 uni.request({ header: { content-type: application/x-www-form-urlencoded; charsetUTF-8},url: ,method:POST, //请求方式POST\GETdata:that.loginData,success: funct…...
酷开科技服务升级,酷开系统给消费者更好的使用体验!
看电视的时候你是不是也会有选择困难症?不知道要看哪个?不知道如何操作?体验不够顺畅?现在,有了酷开系统9.2,这些通通不再是问题!酷开科技,一直致力于服务升级,给消费者更…...
【leetcode热题】单词拆分
难度: 中等通过率: 33.7%题目链接:. - 力扣(LeetCode) 题目描述 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明&#…...
【论文阅读】MC:用于语义图像分割的深度卷积网络弱监督和半监督学习
【论文阅读】MC:用于语义图像分割的深度卷积网络弱监督和半监督学习 文章目录 【论文阅读】MC:用于语义图像分割的深度卷积网络弱监督和半监督学习一、介绍二、联系工作三、方法四、实验结果 Weakly- and Semi-Supervised Learning of a Deep Convolutio…...
读书·基于RISC-V和FPGA的嵌入式系统设计·第3章
72.8051单片机的弊端和指令集架构CISC的缺点 76.RV指令集的特征(⭐) 特权架构和特权指令集是相关但不完全相同的概念。 特权架构(Privileged Architecture)指的是计算机体系结构中用于实现特权级操作的硬件和软件机制。特权架构定…...
本地项目推送到腾讯云轻量应用服务器教程(并实现本地推送远程自动更新)
将本地项目上传到腾讯云轻量应用服务器并实现后续的推送更新,具体步骤如下: 在本地项目目录下初始化 Git 仓库: cd 项目目录 git init将项目文件添加到 Git 仓库并提交: git add . git commit -m "Initial commit"在…...
MacOS安装反编译工具JD-GUI 版本需要1.8+
Java Decompiler http://java-decompiler.github.io/ 将下载下来的 jd-gui-osx-1.6.6.tar 解压,然后将 JD-GUI.app 文件拷贝到 Applications 应用程序目录里面 1.显示包内容 2.找到Contents/MacOS/universalJavaApplicationStub.sh 3.修改sh文件 内容修改为下面…...
计算机大数据毕业设计-基于Flask的旅游推荐可视化系统的设计与实现
基于Flask的旅游推荐可视化系统的设计与实现 编程语言:Python3.10 涉及技术:FlaskMySQL8.0Echarts 开发工具:PyCharm 摘要:以Pycharm为旅游推荐系统开发工具,采用B/S结构,使用Python语言开发旅游景点推…...
java实现pdf转word
java实现pdf转word 前言pom文件启动入口过滤器对象ConvertPdfToWordWithFlowableStructure转换实现类 前言 1.java实现pdf转word。 2.纯免费开源。 3.pdf解析完会生成word文件和图片文件夹。 4.无页码限制,文本类型生成到word中,图片生成到图片文件夹中…...
【操作系统概念】 第4章:线程
文章目录 0.前言4.1 概述4.1.1 多线程编程的优点 4.2 多线程模型4.2.1 多对一模型4.2.2 一对一模型4.2.3 多对多模型 4.3 线程库4.4 多线程问题4.4.1 系统调用fork()和exec()4.4.2 取消4.4.3 信号处理4.4.4 线程池4.4.5 线程特定数据 0.前言 第3章讨论的进程模型假设每个进程是…...
STM32/GD32——I2C通信协议
芯片选型 Ciga Device — GD32F470系列 通讯规则 I2C协议(或称IIC)是由飞利浦(现在的恩智浦半导体)公司开发的一种通用的总线协议。它使用两根线(时钟线和数据线)来传输数据,支持多个设备共享…...
Apache Paimon 使用之Creating Catalogs
Paimon Catalog 目前支持两种类型的metastores: filesystem metastore (default),在文件系统中存储元数据和表文件。 hive metastore,将metadata存储在Hive metastore中。用户可以直接从Hive访问表。 1.使用 Filesystem Metastore 创建 Cat…...
IntelliJ IDEA分支svn
IntelliJ IDEA分支svn 【为何使用分支】 项目开发中经常会遇到这种情况,项目中功能开发完上线后,新的需求又来了,风风火火的在项目里开发, 突然有一天测试说有个很致命的bug需要紧急修改上线,完蛋了,原来…...
.NET Core日志内容详解,详解不同日志级别的区别和有关日志记录的实用工具和第三方库详解与示例
在本文中,我们将详细介绍.NET Core日志内容,包括不同日志级别的区别,以及一些常用的日志记录实用工具和第三方库。同时,我们还将通过示例来展示如何使用这些工具和库。 一、.NET Core日志级别 .NET Core日志系统提供了五种日志级…...
Vue开发实例(七)Axios的安装与使用
说明: 如果只是在前端,axios常常需要结合mockjs使用,如果是前后端分离,就需要调用对应的接口,获取参数,传递参数;由于此文章只涉及前端,所以我们需要结合mockjs使用;由于…...
2024.3.6
作业1:使用C语言完成数据库的增删改 #include <myhead.h>//定义添加员工信息函数 int Add_worker(sqlite3 *ppDb) {//准备sql语句printf("请输入要添加的员工信息:\n");//从终端获取员工信息char rbuf[128]"";fgets(rbuf,sizeof(rbuf),s…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权
摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题:安全。文章将详细阐述认证(Authentication) 与授权(Authorization的核心概念,对比传统 Session-Cookie 与现代 JWT(JS…...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...
