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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

Solution

官方题解思路：哈希表

• 我们将数组中所有小于等于 0 的数修改为 N+1；

• 我们遍历数组中的每一个数 x，它可能已经被打了标记，因此原本对应的数为 |x|，其中 ∣∣ 为绝对值符号。如果 ∣x∣∈[1,N]，那么我们给数组中的第 |x| - 1 个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；

• 在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 N+1，否则答案是第一个正数的位置加 1。

# @lc code=start
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        if not nums:
            return 1
        n = len(nums)
        for i in range(n):
            if nums[i] <= 0:
                nums[i] = n+1
        
        for i in range(n):
            num = abs(nums[i])
            if num <= n:
                nums[num-1] = -abs(nums[num-1])

        for i in range(n):
            if nums[i] > 0:
                return i+1
        
        return n
# @lc code=end

思路二：使用置换

• 如果数组中包含 x∈[1,N]，那么恢复后，数组的第 x - 1个元素为 x。因此交换 $\textit{nums}[i]$ 和$nums[x−1] $ ，这样 x 就出现在了正确的位置。在完成交换后，新的 $\textit{nums}[i]$ 可能还在 [1,N] 的范围内，我们需要继续进行交换操作，直到 $x \notin [1, N]$。
• 如果 $\textit{nums}[i]$恰好与$ \textit{nums}[x - 1]$ 相等，那么就会无限交换下去。此时我们有 $\textit{nums}[i] = x = \textit{nums}[x - 1]$，说明 x 已经出现在了正确的位置。因此我们可以跳出循环，开始遍历下一个数。

此题原地置换思路与442题方法二有相似之处，由于数组元素没有 1<= a[i] <= n 限制，故还应该加上 1 <= nums[i] <= n。

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

        return n+1