41.缺失的第一个正数

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

·题目描述

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。示例 1：输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
示例 2：输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。
示例 3：输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

·解题思路——要求时间复杂度O（n），空间复杂度O（1）

1.我们所需要排查的数字范围为[1,len(nums)]。

2.利用数字和下标的关系。将数字大小-1与下标位置相对应。因此需要交换位置。满足交换条件的数字大小为，在所需要范围内、与坐标不对应因此需要交换。

3.时间复杂度在交换时候的优化。涉及到两个数字的交换，有可能出现一个是满足坐标要求，而另外一个不满足，因此判断条件涉及两个

4.再次遍历。如果交换完还是不符合坐标数字要求，则返回缺失。

·代码

class Solution(object):def firstMissingPositive(self, nums):n = len(nums)for i in range(n):while nums[i] != i + 1 and 0<= nums[i]< n and nums[nums[i]- 1] != nums[i]:nums[nums[i] - 1],nums[i]  =nums[i], nums[nums[i] - 1]for i in range(n):if (i + 1) != nums[i]:return i + 1return n+1

————只涉及两个循环————

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

---