【LeetCode】0041 缺失的第一个正数

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

# -*- coding:utf-8 -*-

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        temp_list = [0 for _ in range(n)]
        for each in nums:
            if each <= n and each > 0:
                temp_list[each - 1] = each
        for i in range(n):
            if temp_list[i] != i + 1:
                return i + 1
        return n + 1
if __name__ == '__main__':
    nums = [1]
    print(Solution().firstMissingPositive(nums))

思路：这道题首先生成一个长度为n的列表，然后遍历整个数组，将>0并且<n的数字放入列表中，如果有位置为初始值0，则说明缺少这个，如果列表没有缺失位置，则说明缺失值为n+1。

这个方法空间和时间复杂度都为O(n)。但是题里说线性空间，那么我们可以提前遍历一遍数组，求出正数和个数，这样就可以把n缩小，空间复杂度也将为了常数。

这是典型的时间换空间的做法，实际上不做处理也可以达到一个很好的效果。