Leetcode41缺失的第一个正数

2023-11-05 13:04

本文主要是介绍Leetcode41缺失的第一个正数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

思路:原地哈希表

长度为N的数组,没有出现过的正整数一定是1~N+1中的一个。

此时会思考能不能用一个哈希表来保存出现过的1~N+1的数,然后从 1 开始依次枚举正整数,并判断其是否在哈希表中

但是题目要求常数级别的空间,就不能使用N的哈希表了。

这里将原数组当做哈希表,使用标记的办法来标记出现过的正整数,最后遍历数组,第一个没出现的下标+1就是答案

怎么样进行标记呢?

  • 先遍历一遍数组,将非正整数置为N+1
  • 再遍历一遍数组,将1~N正整数对应的下标位置置为负数
  • 最后遍历一遍数组,第一个不是负数的位置i+1就是没出现过的最小的正整数

 

class Solution {public int firstMissingPositive(int[] nums) {int len = nums.length;for(int i = 0;i<len;i++){if(nums[i]<=0){nums[i] = len+1;}}for(int i = 0;i<len;i++){int num = Math.abs(nums[i]);if(num<=len&&num>0){nums[num-1] = -Math.abs(nums[num-1]);}}for(int i = 0;i<len;i++){if(nums[i]>=0){return i+1;}}return len+1;} 
}

这篇关于Leetcode41缺失的第一个正数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

电脑提示Winmm.dll缺失怎么办? Winmm.dll文件丢失的多种修复技巧

《电脑提示Winmm.dll缺失怎么办?Winmm.dll文件丢失的多种修复技巧》有时电脑会出现无法启动程序,因为计算机中丢失winmm.dll的情况,其实,winmm.dll丢失是一个比较常见的问... 在大部分情况下出现我们运行或安装软件,游戏出现提示丢失某些DLL文件或OCX文件的原因可能是原始安装包

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

电脑开机提示krpt.dll丢失怎么解决? krpt.dll文件缺失的多种解决办法

《电脑开机提示krpt.dll丢失怎么解决?krpt.dll文件缺失的多种解决办法》krpt.dll是Windows操作系统中的一个动态链接库文件,它对于系统的正常运行起着重要的作用,本文将详细介绍... 在使用 Windows 操作系统的过程中,用户有时会遇到各种错误提示,其中“找不到 krpt.dll”

电脑报错cxcore100.dll丢失怎么办? 多种免费修复缺失的cxcore100.dll文件的技巧

《电脑报错cxcore100.dll丢失怎么办?多种免费修复缺失的cxcore100.dll文件的技巧》你是否也遇到过“由于找不到cxcore100.dll,无法继续执行代码,重新安装程序可能会解... 当电脑报错“cxcore100.dll未找到”时,这通常意味着系统无法找到或加载这编程个必要的动态链接库

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

Spring Roo 实站( 一 )部署安装 第一个示例程序

转自:http://blog.csdn.net/jun55xiu/article/details/9380213 一:安装 注:可以参与官网spring-roo: static.springsource.org/spring-roo/reference/html/intro.html#intro-exploring-sampleROO_OPTS http://stati

使用gradle做第一个java项目

涉及到的任务如下: assemble任务会编译程序中的源代码,并打包生成Jar文件,这个任务不执行单元测试。 Total time: 5.581 secs E:\workspace\Test>gradle assemble :compileJava :processResources UP-TO-DATE :classes :findMainClass :jar :b

vue2实践:第一个非正规的自定义组件-动态表单对话框

前言 vue一个很重要的概念就是组件,作为一个没有经历过前几代前端开发的我来说,不太能理解它所带来的“进步”,但是,将它与后端c++、java类比,我感觉,组件就像是这些语言中的类和对象的概念,通过封装好的组件(类),可以通过挂载的方式,非常方便的调用其提供的功能,而不必重新写一遍实现逻辑。 我们常用的element UI就是由饿了么所提供的组件库,但是在项目开发中,我们可能还需要额外地定义一

SpringMVC的第一个案例 Helloword 步骤

第一步:web.xml配置 <?xml version="1.0" encoding="UTF-8"?> <web-app version="2.5" xmlns="http://java.sun.com/xml/ns/javaee" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocati

我的第一次份实习工作-iOS实习生-第一个月

实习时间:2015-08-20 到 2015-12-25  实习公司;福建天棣互联有限公司 实习岗位:iOS开发实习生 第一个月: 第一天来公司,前台报道后,人资带我去我工作的地方。到了那,就由一个组长带我,当时还没有我的办公桌,组长在第三排给我找了一个位置,擦了下桌子,把旁边的准备的电脑帮我装了下,因为学的是iOS,实习生就只能用黑苹果了,这是我实习用的电脑。 帮我装了一下电脑后,开机