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
Note:
Your algorithm should run in O(n) time and uses constant extra space.
Resolution:
Python里面最简单的方法如下。但是最坏情况下复杂度有O(N^2)，因为__ contains __这个就有O(N)
class Solution:
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 1
for i in range(1,max(nums)+2):
if not nums.__contains__(i):
return i
所以换了一种方法。简直机智到哭orz。理解的方法如下：
因为nums数字的正负后面要用来判断，所以我们需要先筛出正数的数目（假设为k），并且排到nums的前面[0:k-1]位。
根据鸽笼原理，一共有k个正数，那么从1到k+1里面，一定有至少一个正数没有出现过。
于是我们遍历nums里面的正数，如果这个数字是t，在[1, k]这个范围内，就把t-1下标位置的nums数字置为负数。
然后遍历nums[0: k-1]，遇到的第一个正数的下标+1就是我们要的数。如果所有的书都是负数，那我们要的数就是k+1。
完成！
Code:
def swap(nums, q, i):
tmp = nums[q]
nums[q] = nums[i]
nums[i] = tmp
def rearange(nums):
q = 0
for i, c in enumerate(nums):
if nums[i]>0:
swap(nums, q, i)
q += 1
return q
class Solution:
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
pivot = rearange(nums)
# pivot is the number of positive number
for i, c in enumerate(nums[:pivot]):
if c <= pivot:
if nums[c-1] > 0:
nums[c-1] *= -1
for i in range(pivot):
if nums[i] > 0:
return i+1
return pivot+1