原题
给出一个无序的正数数组，找出其中没有出现的最小正整数。
如果给出 [1,2,0], return 3 如果给出 [3,4,-1,1], return 2
只允许时间复杂度O(n)的算法，并且只能使用常数级别的空间。
解题思路
- 类似于桶排序的思路，对于每一个整数，我们按照一定的规则放到相应的位置上，最后再去检查如果指定位置的数不存在，即为没有出现的最小正整数
- 规则：1放在array[0]，2放在array[1]，以此类推
对于[3, 4, -1, 1]，运行最终结果为[1, -1, 3, 4]所以检查到array[1]时，2不存在，2即为没有出现的最小正整数 - 注意，遍历数组是，对于每一位要while循环至该位置的数字放到正确的位置为止
while nums[i] <= len(nums) and nums[i] > 0 and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
完整代码
class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 1
for i in range(len(nums)):
while nums[i] <= len(nums) and nums[i] > 0 and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i in range(len(nums)):
if nums[i] != i + 1:
return i + 1
return len(nums) + 1
