###### tags: `Leetcode` `hard` `array` `python` `Top 100 Liked Questions`

# 41. First Missing Positive

## [題目來源:] https://leetcode.com/problems/first-missing-positive/

## 題目:
Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that **runs in O(n) time and uses constant extra space.**


#### [圖片來源] https://leetcode.com/problems/first-missing-positive/

## 解題想法:
* 要求 time:O(n) space:O(1)
* 從1開始找有無出現
* 正常來說 最大找不到的數 一定是len(nums)+1
* ex:[1,2,3,4] => 5一定不在
* 所有負數、0、大於len(nums)+1的數都不用考慮
* 將出現的數字 其應該放入的正確位置進行標記:
* ex: [0,3,1,2]=>應該為[0,1,2,3] 3應該要在nums[3]

## Python:

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #linear search nums 
        #若為1~len(nums) 則在find[i]處=1
        nums.append(0)
        if len(nums)==1:
            return 1
        for i in range(len(nums)): #將不用考慮的數都設0
            if nums[i]<0 or nums[i]>=len(nums):
                nums[i]=0
        #將出現的數字 其應該放入的正確位置進行標記:
        #ex: [0,3,1,2]=>應該為[0,1,2,3] 3應該要在nums[3]
        #作法: 同加一個數 每次求在%即可
        for i in range(len(nums)):
            nums[nums[i]%(len(nums))]+=len(nums)
        #找第一個==0的
        for pos in range(1,len(nums)):
            if nums[pos]<len(nums): #表示該pos原本住的是別人家的
                return pos
        return len(nums)

result=Solution()
ans=result.firstMissingPositive(nums=[3,2,0])
print(ans)