[LeetCode]题解（python）：041-First Missing Positive

题目来源

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

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

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

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

题意分析

Input:a list with many numbers

Output:the first missing positive number

Conditions:最小的missing 正整数，注意要0（n）级别的算法

题目思路

利用字典去做，因为字典查询是0（n）的，不过会使用0（n）的空间，AC了，但是网上说要用triky，可能是leecode评测放宽了……以后再回来看看

AC代码（Python）

 1 _author_ = "YE"
 2 # -*- coding:utf-8 -*-
 3 
 4 class Solution(object):
 5     def firstMissingPositive(self, nums):
 6         """
 7         :type nums: List[int]
 8         :rtype: int
 9         """
10         len1 = len(nums)
11         if len1 == 0:
12             return 1
13         dic = {}
14         for num in nums:
15             if num > 0:
16                 dic[num] = num
17         for i in range(1, len1 + 1):
18             if dic.get(i, -1) == -1:
19                 return i
20         return len1 + 1