假设我们有一个未排序的整数数组;我们必须找到最小的缺失正数。因此,如果数组类似于[4,-3,1,-1],则结果将为2。
为了解决这个问题,我们将遵循以下步骤-
设置i:= 0并通过在所有数字之前加一个0来更新数组nums
对于范围从0到nums的i
nums [nums [i]]:= nums [i]
nums [i]:= nums [nums [i]]
而nums [i]> = 0且nums [i] <nums的长度和nums [nums [i]]不是nums [i]-
num:= 1
对于范围从1到nums的i
如果num = nums [i],则将num加1
返回数字
让我们看下面的实现以更好地理解-
class Solution(object): def firstMissingPositive(self, nums): i = 0 nums = [0] + nums for i in range(len(nums)): while nums[i]>=0 and nums[i]<len(nums) and nums[nums[i]]!=nums[i]: nums[nums[i]],nums[i] = nums[i],nums[nums[i]] num = 1 for i in range(1,len(nums)): if num == nums[i]: num+=1 return num ob = Solution()print(ob.firstMissingPositive([4,-3,1,-1]))
[4,-3,1,-1]
输出结果
2