1.题目基本信息

1.1.题目描述

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

1.2.题目地址

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

2.解题方法

2.1.解题思路

置换（时间复杂度：O(n)，空间复杂度：O(1)）

2.2.解题步骤

第一步。将数组所有大于length的全部标记为负号，因为这些数字不可能是结果，从而保证在[0:length]闭区间中的数字为正号

第二步，恢复。移动大小在[0,length]闭区间中的nums[i]数字到nums[i]-1的指针位置，这就是恢复的步骤

2.1.将在[1,...,length]范围内的两个数字进行置换恢复，对于相等或者超过范围的数字不处理

第三步，找出恢复后的数组中与索引不匹配的第一个数字的索引，即为题解

3.解题代码

Python代码

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # 思路：置换
        length=len(nums)
        # 第一步。将数组所有大于length的全部标记为负号，因为这些数字不可能是结果，从而保证在[0:length]闭区间中的数字为正号
        for i in range(length):
            if nums[i] > length:
                nums[i] = -nums[i]
        # 第二步，恢复。移动大小在[0,length]闭区间中的nums[i]数字到nums[i]-1的指针位置，这就是恢复的步骤
        for i in range(length):
            j = nums[i] - 1
            # 2.1.将在[1,...,length]范围内的两个数字进行置换恢复，对于相等或者超过范围的数字不处理
            while 0 <= j < length and nums[i] != nums[j]:
                # print("t1", i, j)
                nums[i], nums[j] = nums[j], nums[i]
                j = nums[i] - 1
        # 第三步，找出恢复后的数组中与索引不匹配的第一个数字的索引，即为题解
        result = -1
        for i in range(length):
            if nums[i] != i + 1:
                result = i + 1
                break
        result = result if result != -1 else length + 1
        # print(nums)
        # print(result)
        return result

4.执行结果