题目: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 没有出现。
提示:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
一、模式识别
本题较难,无法直接找到模式,需要单独分析:
题解原话:
「真正」满足时间复杂度为 O(N) 且空间复杂度为 O(1) 的算法是不存在的,但是我们可以退而求其次:利用给定数组中的空间来存储一些状态。也就是说,如果题目给定的数组是不可修改的,那么就不存在满足时空复杂度要求的算法;但如果我们可以修改给定的数组,那么是存在满足要求的算法的。
思路一:把nums从数组变成集合(不知道算不算?),这样就可以ON线性遍历查找了
思路二:从 1 开始依次枚举正整数,并遍历数组,判断其是否在数组中
遍历数组找数字,排除其他数字,将[1, N]内的数字放入对应索引位置,
我这里用一下官方题解的图:
二、代码实现
1.数组变集合
class Solution:def firstMissingPositive(self, nums: List[int]) -> int:nums = set(nums)ans = 1while ans in nums: ans += 1return ans
2.多次遍历标记数组
class Solution:def firstMissingPositive(self, nums: List[int]) -> int:n = len(nums)for i in range(n):if nums[i] <= 0: nums[i] = n + 1for i in range(n):num = abs(nums[i])if num <= n: nums[num - 1] = -abs(nums[num - 1])for i in range(n):if nums[i] > 0: return i + 1return n + 1
3.置换数组
class Solution:def firstMissingPositive(self, nums: List[int]) -> int:n = len(nums)for i in range(n):while 1 <= 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 nums[i] != i + 1: return i + 1return n + 1