缺失的第一个正整数

[编程题]缺失的第一个正整数

热度指数：77277 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

数据范围:

$-2^{31}\le nums[i] \le 2^{31}-1$

$0\le len(nums)\le5*10^5$

示例1

输入

[1,0,2]

输出

示例2

输入

[-2,3,4,1,5]

输出

示例3

输入

[4,5,6,8,9]

输出

算法知识视频讲解

牛客题解官

发表于 2022-04-22 12:24:35

精华题解题目主要信息: 题目给定一个无序整型数组，没有重复元素，可能有负数或零，需要找出其中没有出现的最小正整数举一反三：学习完本题的思路你可以解决如下题目： BM51. 数组中出现次数超过一半的数字 BM52. 数组中只出现一次的两个数字方法一：哈希表（推荐使用）知识点：哈希表哈希表是一种根展开全文

不想看论文

发表于 2022-04-04 12:36:40

理想情况下每个元素都在自己的位置上，如下：现在将元素对应位置打乱，并且缺失了一个元素，如下：那么怎么找到这个缺失元素呢？我们可以依次遍历数组 nums ，每遍历到一个元素，比如 nums[i] ，就将 nums[i] 的值对应的位置做上标记，表示这个位置上的主人出现过，只是现在不在这个位置。展开全文

//returnasea

发表于 2021-10-06 21:00:31

nums的长度为n，所以缺失的第一个正整数要么在[1,n]中，要么是n+1。将nums中的负数修改为n+1，然后遍历nums数组，当碰到的元素<=n时，表示此元素在[1,n]中出现过，将它标记为负数。再次遍历nums碰到的第一个非负数的下标表示没有出现过，否则未出现的元素为n+1。 class 展开全文

jxust18A

发表于 2021-11-02 21:55:33

主要思想就是，如果找最小未出现的正整数，必然在1~n+1中，所以对于所有a[i]，如果a[i]在[1,n]中，那么就放到这个位置上去，否则大于n或者小于1的话，就不管它， O(n)复杂度 class Solution { public: /** * 代码中的类名、方法名、参数名已经展开全文

2019113916

发表于 2021-10-03 22:26:39

题意概述给定一个无重复的整数数组找出其中没有出现的最小正整数方法一：哈希思路与具体做法首先遍历整个数组，并用unordered_map标记该数字已出现然后从1遍历到n，并在unordered_map查找该值是否出现，未出现则直接返回若长度为n的数组里n个数字都出现了，则第n+1个展开全文

空中转体一周半

发表于 2022-01-03 23:07:18

时间复杂度O(n),空间复杂度O(n)的做法：开辟一个新的数组arr，长度为nums.length+1，遍历nums数组，如果非负且值小于nums的长度，则把arr[nums[i]]置1。然后遍历辅助数组，找到下标不为1的第一个元素即可。 public class Solution { pu 展开全文