Array
041. First Missing Positive
Given an unsorted integer array, find the smallest missing positive integer.
就是 给一个整数数组，找到数组中缺少的最小正整数
我的理解：
如果这个数组中没有1，那么这个最小正整数就应该是1，
如果数组里面有1，那么当第一次有连续两个整数之间差值大于1时(前提是数组有序)，缺失的最小正整数应该为前一个数加1，否则，如果数组是连续整数，那么缺失的最小值为最后一个数+1
然后就写出了一段很蠢的代码
class Solution:
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
if 1 not in nums:
return 1
elif len(nums)==1:
return 2
else:
for i in range(len(nums)-1):
if nums[i]<0:
continue
if nums[i]<nums[i+1]-1:
return nums[i]+1
return nums[-1]+1
参考了别人的代码，发现我的想法太直接了，傻呀
这段代码的核心思想是，遍历整个数组使得第i个位置上存放的值是i+1，然后再遍历一遍，返回第一个不符合前述条件的i+1
class Solution:
def firstMissingPositive(self, A):
i = 0
while i < len(A):
if A[i] > 0 and A[i] - 1 < len(A) and A[i] != A[A[i]-1]:
A[A[i]-1], A[i] = A[i], A[A[i]-1]
else:
i += 1
for i, integer in enumerate(A):
if integer != i + 1:
return i + 1
return len(A) + 1
