Array-T41. First Missing Positive

Problem：Given an unsorted integer array, find the smallest missing positive integer.

Note:

Your algorithm should run in O(n) time and uses constant extra space.

Solve：(复杂度为O(nlogn))

Thought：由于所给的列表为无序列表，且涉及最值问题，所以先对列表进行排序。设置一个变量来储存当前未出现的最小正整数。遍历列表即可找出缺少的最小正整数。

Solve :（复杂度为O(n)）

class Solution(object):def firstMissingPositive(self, nums):""":type nums: List[int]:rtype: int"""length = len(nums)for i, num in enumerate(nums) :while (num <= length) and (num > 0) and (nums[num - 1] != num) :nums[num - 1], num = num, nums[num - 1]for i in range(length) :if nums[i] != (i + 1) :return i + 1return length + 1

Thought：将每一个在大小范围内的数放到对应的位置上，如数字4放在index为3的位置，跳过其他不在列表长度范围内的数。最后遍历一遍列表，第一个不符合的index+1为缺失的最小正整数。

（注意：数字范围为[1，n]）

关于第二种解法的算法复杂度，由于遍历了两遍，所以至少为O(2n)。而交换的部分，最大交换次数的情况为所有的数均在列表长度内时，需要交换n次（每交换一次就至少有一个数在正确位置上）。总计为O(3n) = O(n)。

既然是用python，肯定会有的必要环节，下面是python的一行代码

class Solution(object):def firstMissingPositive(self, nums):""":type nums: List[int]:rtype: int"""return min(set(range(1, len(nums) + 2)) - set(nums))