41. First Missing Positive

总结：找到一个无序的列表里<u>空缺的最小的正整数</u>

解法：

1.排序之后找最小正数

描述： 对一个有序的列表，从最小的正整数1开始依次判断，看是否是空缺的数。遍历列表，只针对正数开始判断，如果该数小于列表中的数，那就是结果。如果该数等于列表中的数，那说明不是空缺的，该数+1，继续判断。不会出现该数大于列表中的数的情况。

例子

        nums = sorted(nums)
        j = 1
        for i in nums:
            if i > 0:
                if i > j:
                    break
                j = i + 1
        return j

2.把每个元素放置在“正确”的位置上。（适合找空缺的题）/循环替换

中心思想：

1，如果每个元素n 都放在正确的位置 index n-1 上，只需要从1开始到len（nums）遍历一遍，哪个index上的数字不对，这个index+1就是空缺的最小整数。

2，并且空缺的最小正整数只会在“1,len(nums)+1”(极端情况下 [1,2]空缺是3)

3.任何负数包括0和任何大于len(nums)的数不会对结果造成影响 ([-9999,1,2,3]空缺是4 [1,2,3,9999]结果是4)

思路：

循环替换，从第一个元素n开始，找到它应该放置的位置（index为n-1），将index n-1位置的元素放置到临时变量中，将n放置在该位置。再找临时变量中元素的正确位置，以此类推，当正确位置的index大于len（nums）-1，则跳过。当正确位置的index小于0，则跳过。遇上正确的元素也跳过。跳过之后，对下一个元素循环替换。

例子

for i, v in enumerate(nums):
    if i != v - 1:
        prev = v
        while (True):
            if prev - 1 < 0 or prev - 1 >= len(nums) or nums[prev - 1] == prev:
                break
            t = nums[prev - 1]  # 因为数组下标也用到了prev python自带的交换变量方法会出错
            nums[prev - 1] = prev
            prev = t
for n in range(len(nums)):
    if nums[n] != n + 1:
        return n + 1
return len(nums)+1