leetcode [41] 缺失的第一个正数

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

示例 1:

输入: [1,2,0]
输出: 3

示例 2:

输入: [3,4,-1,1]
输出: 2

示例 3:

输入: [7,8,9,11,12]
输出: 1

说明:

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

先做预处理，去掉小于等于0的。最小值如果不是1，可以直接返回1。然后减去最小值（1），让数以0开始，这样可以对应到下标。遍历，如果下标不等于值，那么和值为下标的数交换。为了避免遇到交换死循环，如果碰到值大于数组容纳范围或者交换相等的情况，退出交换。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        nums = [n for n in nums if n > 0]
        if len(nums) == 0:
            return 1
        minvalue = min(nums)
        if minvalue != 1:
            return 1
        nums = [n - minvalue for n in nums]
        i = 0
        for i, n in enumerate(nums):
            while nums[i] != i:
                if nums[i] >= len(nums) or nums[i] == nums[nums[i]]:
                    break
                j = nums[i]
                nums[i], nums[j] = nums[j], nums[i]
        for i, n in enumerate(nums):
            if i != n:
                return i + minvalue
        return len(nums) + minvalue