41.py

'''
 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
'''
classSolution(object):
deffirstMissingPositive(self, nums):
"""
 :type nums: List[int]
 :rtype: int
 """
index_i=0
forindex_jinrange(len(nums)):
ifnums[index_j] <=0:
nums[index_i], nums[index_j] =nums[index_j], nums[index_i]
index_i+=1

forindexinrange(index_i, len(nums)):
ifabs(nums[index]) -1<len(nums) andnums[abs(nums[index]) -1] >0:
nums[abs(nums[index]) -1] =-nums[abs(nums[index]) -1]

forindexinrange(nums):
ifnums[index] >0:
returnindex+1
returnlen(nums) +1