leetcode题解41：缺失的第一个正数

描述

该题来自于力扣第41题

分析

没有出现的最小的正整数，按照暴力法就是先判断1有没有在，没有则返回1，有则继续判断2，依次下去；但是有更好的方法，假设没有出现的最小正整数为n，表示1～n-1都在数组中，那么如果将k放到数组的k-1位置上，即arr[k-1]=k，其中arr为数组，数组的前n-1个数就是1,2,...,n-1，由于n不在数组中，那么arr[n-1]必不等于n。那么求解过程应该是
1. 遍历到i处，如果1<=arr[i]<=len(arr)，表示arr[i]应该放到arr[i]-1这个位置上，但是首先判断arr[i]-1是否已经是arr[i]，如果是的话不进行操作，继续遍历下一个；如果不是则交换i与arr[i]-1位置上的两个数，继续遍历下一个；
2. 当遍历完整个数组后，第一个不满足arr[k-1]==k的k就是解了；如果都满足表示1~len(arr)都在数组中，那么解就是len(arr)+1。

代码

python

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        i = len(nums) - 1
        while i >= 0:
            if 0 <= nums[i] - 1 < len(nums) and nums[nums[i]-1] != nums[i]:
                j = nums[i] - 1
                nums[i], nums[j] = nums[j], nums[i]
            else:
                i -= 1
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1
        return len(nums) + 1