本文共 681 字，大约阅读时间需要 2 分钟。

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]Output: 3

Example 2:

Input: [3,4,-1,1]Output: 2

Example 3:

Input: [7,8,9,11,12]Output: 1

找到第一个缺失的正数。

有很多种方法，但是要求O(n) time and uses constant extra space。

我用一个bool的数组记录每个数字出现，然后返回第一个为False的数字。

记录过程中去掉小于0的数和大于len(nums)的数。如果全是True就返回len(nums)+1，因为正数从1开始而不是0。

class Solution:    def firstMissingPositive(self, nums: List[int]) -> int:        l=len(nums)+1        dp=[True]+[False for _ in range(l-1)]        for num in nums:            if num<0 or num>l-1:continue            dp[num]=True        for i in range(l):            if dp[i] is False:                return i        return l

转载地址：http://pcrbb.baihongyu.com/