电商模板网站中国宣布取消新冠免费治疗
代码
测试用例
测试用例
测试结果
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
class Solution(object):def firstMissingPositive(self, nums):""":type nums: List[int]:rtype: int"""# 得到最大值，正数最小值# 不能排序，因为排序nlogn# 只能利用原本的数字存储了for i ,val in enumerate(nums):while nums[i]>0 and nums[i]<=len(nums) and nums[i]!=i+1 and nums[nums[i]-1] != nums[i]:temp = nums[i]nums[i] = nums[temp-1]nums[temp-1] = tempfor i in range(len(nums)):if nums[i]!=i+1:return i+1return len(nums)+1首先题目的要求是空间为常熟
所以不能使用hash表
那么我们只能用原本的数组去处理了
所以我们的方法是把符合条件的正整数也就是1-》len(nums)的数放到他的值减一的下标处，这样遍历一遍就知道少了哪个了。
需要考虑多种情况
1. 当你把一个数换过去之后，换回来的数还需要继续换，所以我们的for里面用while处理
2. 当你把数换过来之后可能那个地方本来就已经有一个数占据位置了，也就是[1,1]的情况，这样会导致死循环，所以你需要把这种情况当做看不见。因为放到原处，也是一个不合理值，反正要放到的地方已经有合理值了。