041._First_Missing_Positive.md

41. First Missing Positive

难度: 困难

刷题内容

原题连接

• https://leetcode.com/problems/first-missing-positive

内容描述

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
Note:

Your algorithm should run in O(n) time and uses constant extra space.

解题方案

思路 1

题目要求O(n)时间和O(1)空间，所以我们知道先排序再循环找是不行的

因此我们可以这样，第一轮循环，找1(因为1是最小的正整数)，如果1在，立马原地开始继续找2，以此类推，一轮循环结束后，我们记录下当前正在找的值i， 并开始第二轮循环，但是这次从i开始找了，然后以此类推，直到有一次循环我们要找的值没有变过，则代表它没出现过，返回它即可

可以看一个例子

[3,4,-1,1]

第一轮循环：[1,1,1,2]
第二轮循环：[2,2,2,2]

然后我们发现第二轮循环2没有变过了，所以2就是我们要的结果

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        old_missing, missing = 0, 1
        while old_missing != missing:
            old_missing = missing
            for i in range(len(nums)):
                if nums[i] == missing:
                    missing += 1
        return missing

思路 2

如果不限制空间的话，我们用一个dict就可以解决, 时间是O(N)

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 1
        lookup = {}
        for i in nums:
            lookup[i] = 1
        for i in range(1, max(nums)+2):
            if i not in lookup:
                return i