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
方法一：暴力解题，复杂度超出范围
from typing import List
def firstMissingPositive(nums: List[int]) -> int:
for i in nums:
if i<0:
nums.remove(i)
nums.sort()
b = []
for i in range(0,max(nums)+2):
if i not in nums:
b.append(i)
b.sort()
if b[0]==0:
b.remove(b[0])
if b==[]:
return max(nums)+1
else:
return min(b)
nums=[3,4,-1,1,9,-5]
a=firstMissingPositive(nums)
print(a)
#以上方法判定为超出内存限制！！！！
方法二：
没有排序或者暴力循环
总体思路：
1对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1]中。这是因为如果 [1,N] 都出现了，那么答案是 N+1，否则答案是 [1,N] 中没有出现的最小正整数
2我们对数组进行遍历，对于遍历到的数 x，如果它在 [1,N]的范围内，那么就将数组中的第 x−1个位置（注意：数组下标从 0开始）打上「标记」。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 N+1，否则答案是最小的没有打上标记的位置加 1
3由于我们只在意 [1,N] 中的数，因此我们可以先对数组进行遍历，把不在 [1,N] 范围内的数修改成任意一个大于 N 的数（例如 N+1）。这样一来，数组中的所有数就都是正数了，因此我们就可以将「标记」表示为「负号」
文章来源：https://www.toymoban.com/news/detail-673136.html
from typing import List
def firstMissingPositive(nums: List[int]) -> int:
n = len(nums)
for i in range(n):
if nums[i] <= 0:
nums[i] = n + 1
print(nums)
#凡是0和负数都变为n+1#[3, 4, 7, 1, 9, 7]，因为这里面7和9数字大于n=6，
#后面都会忽略处理它们，因为缺失的第1个正整数不可能是它们.
#除非[1,n]都出现了，那么缺失的第1个正整数会是n+1见下面的return
for i in range(n):
num = abs(nums[i])
#依次处理nums中的值,注意由于下面的处理nums中的值一直在变化
# #但是nums中各个值的绝对值是不变的
print("num:",num)
#核心思路：不管nums如何变化这里num依次取到的值依然是3, 4, 7, 1, 9, 7
# num为3时把第2个位置的数字改为第2个位置中的数字的负数即把7变为-7
#即后面处理的依然可以取到7这个数字，
#又在[1,n]中3处在第3个位置，也就是python列表的第2个位置，这里把第2个位置7标为负数
#意味着第2个位置标记为负数了，则第2个位置上数即2+1=3，即3不可能是缺失的第1个正整数
if num <= n:
nums[num - 1] = -abs(nums[num - 1])
print("nums:",nums)#
for i in range(n):
if nums[i] > 0:
return i + 1
return n + 1
nums=[3,4,-1,1,9,-5]
a=firstMissingPositive(nums)
print(a)#a的范围肯定在[1,n+1]之间
方法三、文章来源地址https://www.toymoban.com/news/detail-673136.html
到了这里，关于力扣数组类题目--41缺失的第一个正数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
