从零学算法41

news/2024/4/13 11:44:30/文章来源:https://blog.csdn.net/m0_53256503/article/details/136393836

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;}
    

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_997436.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

数位dp 笔记

小技巧1:求区间[X, Y]可以转换为求F(Y) - F(X-1) F(X)表示0~X中满足条件的数字个数 小技巧2&#xff1a;可以用树的形式来看 遍历最高位&#xff0c;每一位分为两种情况&#xff1a;未达到上界和达到上界 如果走到右边最底端需加1 度的数量 求给定区间 [X,Y]中满足下列条件的…

Linux——线程同步互斥(线程安全)

线程互斥 进程线程间的互斥相关背景概念 临界资源&#xff1a;多线程执行流共享的资源就叫做临界资源临界区&#xff1a;每个线程内部&#xff0c;访问临界资源的代码&#xff0c;就叫做临界区互斥&#xff1a;任何时刻&#xff0c;互斥保证有且只有一个执行流进入临界区&…

System Verilog学习笔记(十八)——线程控制

线程控制 发生器把激励传给代理时&#xff0c;环境类需要知道发生器什么时候完成任务&#xff0c;以便及时终止测试平台中还在运行的线程&#xff0c;这个过程就需要借助线程间的通信来完成。常用的线程间通信有事件控制、wait语句、SV信箱和旗语等。 Verilog对语句有两种分组…

SpringCloud-数据认证加密总结

一、数据加密认证介绍 在当今分布式系统的日益复杂和信息传递的广泛网络化环境中&#xff0c;确保通信的安全性至关重要。数据的加密和认证作为保障信息传递安全的关键手段&#xff0c;在分布式系统中扮演着不可或缺的角色。Spring Cloud&#xff0c;作为一套构建微服务架构的…

几个市场主流伦敦银交易系统简介

很多人在伦敦银交易中都希望建立一个交易系统&#xff0c;依靠这个系统&#xff0c;我们在市场中能够建立稳定盈利的基础。下面我们就来简单地介绍几个市场主流的伦敦银交易系统。 均线交易系统。这是很多人使用的伦敦银交易系统&#xff0c;一般适用于趋势行情中。均线交易系统…

Java精品项目--第5期基于SpringBoot的高速收费系统的设计分析与实现

项目使用技术栈 SpringBootMavenShiroMySQLMybatis-PlusJavaJDK1.8HTML 系统介绍 项目截图

Docker部署ruoyi前后端分离项目

目录 一. 介绍前后端项目 二. 搭建局域网 2.1 创建网络 2.2 注意点 三. Redis 3.1 安装 3.2 配置redis.conf文件 3.3 测试 四. 安装MySQL 4.1 安装 4.2 配置my2.cnf文件 4.3 充许远程连接 五. 若依部署后端服务 5.1 数据导入 5.2 使用Dockerfile自定义镜像 5.3 运行…

010-内存泄露

内存泄露 概念引起内存泄漏原因解决排查方案 概念 系统进程不再用到的内存&#xff0c;没有及时释放&#xff0c;就叫做内存泄漏&#xff08;memory leak&#xff09;。当内存占用越来越高&#xff0c;轻则影响系统性能&#xff0c;重则导致进程崩溃。 引起内存泄漏原因 全局…

突破编程_前端_JS编程实例(网站标题栏TAB组件)

1 开发目标 实现如下网站标题栏 TAB 组件&#xff1a; 在点击"页面2"选项卡后&#xff0c;TAB 组件会切换对应的面板&#xff1a; 2 详细需求 网站标题栏 TAB 组件该组件需根据客户端提供的参数创建&#xff0c;具备动态构建 TAB 区域、选项卡切换及自定义内容…

Redis(5.0)

1、什么是Redis Redis是一种开源的、基于内存、支持持久化的高性能Key-Value的NoSQL数据库&#xff0c;它同时也提供了多种数据结构来满足不同场景下的数据存储需求。 2、安装Redis&#xff08;Linux&#xff09; 2.1、去官网&#xff08;http://www.redis.cn/&#xff09;下…

腾讯云哪款服务器最便宜划算?2024腾讯云服务器优惠价格表

腾讯云优惠活动2024新春采购节活动上线&#xff0c;云服务器价格已经出来了&#xff0c;云服务器61元一年起&#xff0c;配置和价格基本上和上个月没什么变化&#xff0c;但是新增了8888元代金券和会员续费优惠&#xff0c;腾讯云百科txybk.com整理腾讯云最新优惠活动云服务器配…

图书馆管理系统(2)

接下来实现系统的子菜单&#xff0c;在写一个子模块的时候&#xff0c;其他子模块先屏蔽起来&#xff0c;因为没实现&#xff0c;代码运行就通不过 屏蔽起来写上todo&#xff0c;后面(Ctrl键F)搜索&#xff0c;找todo来实现 先来实现图书管理模块 第一步&#xff0c;先要把图…

缺陷检测:使用PatchCore训练自己的数据集

文章目录 前期准备两种方法 演示运行结果 代码详解见缺陷检测–PatchCore的代码解读 前期准备 必须包含有训练图片&#xff08;无缺陷图片&#xff09;、测试图片&#xff08;缺陷图片&#xff09;和ground_truth&#xff0c;并且ground_truth必须与对应图片的名称相同。 本文…

MCU中断里使用软延时函数delay_ms(u16 x)问题及实例探讨

原贴有误已删&#xff1a;https://blog.csdn.net/weixin_50007421/article/details/136138221 今天完善如下&#xff1a; 本意&#xff1a;只是想表达“复杂系统中断里当然尽量不用软延时函数&#xff0c;但简单系统只要心中有数逻辑清楚实测无妨就完全可行”。 但后来感觉还…

H264的打包,nal,es,pes,pts,dts,ps,ts

编码层次 视频编码层&#xff1a;预测、变换、量化、熵编码等操作slice层&#xff1a;将视频帧分割成若干个编码单元&#xff0c;包含一定数量的宏块&#xff0c;提高编解码的并行性和容错性。NAL层&#xff1a;提升对网络传输和数据存储的亲和性 视频编码层 基准-Baseline …

火柴排队(逆序对 + 离散化)

505. 火柴排队 原题链接 思路 如下是画图分析的一些过程 在这里贪心的思路是排序&#xff0c;然后两个数组都是从小到大那样对应的话最终的答案可达到最小 而我们只能交换相邻的火柴&#xff0c;故在这里先假设一个简化版本&#xff0c;即A有序&#xff0c;而只需要对B进行…

HTML+CSS+BootStrap游乐园官网

一、技术栈 支持pc、pad、手机访问&#xff0c;页面自适应&#xff01;&#xff01; html5cssbootstrapjs 二、项目截图 接受项目定制&#xff0c;站内联系博主&#xff01;&#xff01;&#xff01;

获取别人店铺的所有商品API接口

使用淘宝淘口令接口的步骤通常包括&#xff1a; 注册成为淘宝开放平台的开发者&#xff1a;在淘宝开放平台网站上注册账号并完成认证。 创建应用以获取API密钥&#xff1a;在您的开发者控制台中创建一个应用&#xff0c;并获取用于API调用的密钥&#xff0c;如Client ID和Clie…

机试指南:Ch5:线性数据结构 Ch6:递归与分治

文章目录 第5章 线性数据结构1.向量 vector2.队列 queue(1)队列的特点、应用(2)基本操作(3)例题例题1&#xff1a;约瑟夫问题2 &#xff08;难度&#xff1a;中等&#xff09; (4)习题习题1&#xff1a;排队打饭 &#xff08;难度&#xff1a;中等&#xff09; 3.栈 stack(1)栈…

【微前端】为什么需要微前端

1 什么是微前端 微前端就是将不同的功能按照不同的维度拆分成多个子应用。通过主应用来加载这些子应用。 微前端的核心在于拆&#xff0c;拆完后再合 2. 为什么去使用他 ○ 不同团队间开发同一个应用技术栈不同 ○ 希望每个团队都可以独立开发&#xff0c;独立部署 ○ 项目中…