[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）

---

 _author_ = "YE"

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

 class Solution(object):

     def firstMissingPositive(self, nums):

         """

         :type nums: List[int]

         :rtype: int

         """

         len1 = len(nums)

         if len1 == 0:

             return 1

         dic = {}

         for num in nums:

             if num > 0:

                 dic[num] = num

         for i in range(1, len1 + 1):

             if dic.get(i, -1) == -1:

                 return i

         return len1 + 1