Python 中的第一个缺失的正数

假设我们有一个无序整数数组，我们必须找到最小的缺失正数。因此，如果数组为 [4, -3, 1, -1]，那么结果将为 2。

要解决这个问题，我们将遵循以下步骤 −

  • 设置 i := 0，并在所有数字之前添加一个 0 来更新数组 nums

  • 对于 i 在 0 到 nums 长度范围内

    • while nums[i] >= 0 且 nums[i] < nums 长度且 nums[nums[i]] 不是 nums[i] −

      • nums[nums[i]] := nums[i]

      • nums[i] := nums[nums[i]]

  • num := 1

  • 对于 i 在 1 到 nums 长度范围内

    • 如果 num = nums[i]，则将 num 增加 1

  • 返回 num

示例

让我们看看以下实现以获得更好的理解 −

 现场演示

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

更新于：26-5 月-2020

768 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始使用
广告