41. 缺失的第一个正数

https://leetcode-cn.com/problems/first-missing-positive/

解法一：

把所有正数i放到数组中第i-1个位置上，即理想情况应该是[1,2,3,...]，然后从头遍历，找第一个不符合该条件的，就是没出现的最小正数。

难点在于怎么放。对于给定位置i，其值应该为i+1，同理对于给定值nums[i]，其位置应该为nums[i]-1

从i=0开始遍历数组，若nums[i] == i+1，符合该条件的不用修改；此外非正数也不用修改；还有位置超出数组长度的也不用修改。

若不满足nums[i] == nums[nums[i]-1]，交换这两个数，将i处的数字放到合适位置，使其符合要求（为何用值来确定位置？因为位置是连续的从0~n-1，而值不一定能满足这些位置要求，所以只能根据值来定位）

其余情况直接跳过

此外交换时不能直接用a,b=b,a方式交换，因为下标嵌套了数组，交换过程中已经改变了相应的下标。应该写成函数来处理

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        i = 0
        while i < len(nums):
            if nums[i] == i+1 or nums[i] <= 0 or nums[i]-1 >= len(nums):   #跳过
                i += 1
            elif nums[i] != nums[nums[i]-1]:
                self.swap(nums, i, nums[i] - 1)  # 调用函数交换
            else:
                i += 1
        #第二次遍历
        i = 0
        while i < len(nums) and nums[i] == i+1:
            i += 1
        return i+1

    def swap(self, nums, i, j):  # 交换函数
        nums[i], nums[j] = nums[j], nums[i]