当前位置: 首页> 科技> 能源 > 采购网哪个平台比较好_免费logo设计自动生成u钙网_河南省最新通知_合作seo公司

采购网哪个平台比较好_免费logo设计自动生成u钙网_河南省最新通知_合作seo公司

时间:2025/7/11 20:23:23来源:https://blog.csdn.net/weixin_44610684/article/details/145885448 浏览次数:0次
采购网哪个平台比较好_免费logo设计自动生成u钙网_河南省最新通知_合作seo公司

题目: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

关键字:采购网哪个平台比较好_免费logo设计自动生成u钙网_河南省最新通知_合作seo公司

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: