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

 

示例 1:

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

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

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

提示：

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


"""


#  注意，本题的难点在于，算法的时间复杂度应该在且额外空间只能使用常数级别
#  所以，排序的方法不可以使用，需要额外的方法

'''如果本题没有额外的时空复杂度要求，那么就很容易实现：

我们可以将数组所有的数放入哈希表，随后从 11 开始依次枚举正整数，并判断其是否在哈希表中；

我们可以从 1 开始依次枚举正整数，并遍历数组，判断其是否在数组中。

如果数组的长度为 N，那么第一种做法的时间复杂度为 O(N)，空间复杂度为 O(N)；第二种做法的时间复杂度为O(N2）
 )，空间复杂度为 O(1)。但它们都不满足题目的要求：时间复杂度为 O(N)，空间复杂度为 O(1)。

「真正」满足此要求的算法是不存在的。但是我们可以退而求其次：利用给定数组中的空间来存储一些状态。
也就是说，如果题目给定的数组是不可修改的，那么就不存在满足时空复杂度要求的算法；但如果我们可以修改给定的数组，那么是存在满足要求的算法的。

方法一：哈希表
对于「前言」中提到的第一种做法：

我们可以将数组所有的数放入哈希表，随后从 1开始依次枚举正整数，并判断其是否在哈希表中。

仔细想一想，我们为什么要使用哈希表？这是因为哈希表是一个可以支持快速查找的数据结构：给定一个元素，我们可以在 O(1) 的时间查找该元素是否在哈希表中。
因此，我们可以考虑将给定的数组设计成哈希表的「替代产品」。

实际上，对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中。这是因为如果 [1,N] 都出现了，那么答案是 N+1，
否则答案是 [1,N] 中没有出现的最小正整数。这样一来，我们将所有在 [1,N] 范围内的数放入哈希表，也可以得到最终的答案。
而给定的数组恰好长度为 N，这让我们有了一种将数组设计成哈希表的思路：

我们对数组进行遍历，对于遍历到的数 x，如果它在 [1,N] 的范围内，那么就将数组中的第 x-1 个位置（注意：数组下标从 0 开始）打上「标记」。
在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 N+1，否则答案是最小的没有打上标记的位置加 1。

那么如何设计这个「标记」呢？由于数组中的数没有任何限制，因此这并不是一件容易的事情。
但我们可以继续利用上面的提到的性质：由于我们只在意 [1, N] 中的数，
因此我们可以先对数组进行遍历，把不在[1,N] 范围内的数修改成任意一个大于 N 的数（例如N+1）。
这样一来，数组中的所有数就都是正数了，因此我们就可以将「标记」表示为「负号」。算法的流程如下：

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

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

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


时间复杂度：O(N)，其中 N 是数组的长度。

空间复杂度：O(1)。
'''


class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            if nums[i]<=0:
                nums[i] = n+1
                # 先将负数转换为无关的正数（假设为n+1）
        for i in range(n):
            num = abs(nums[i])
            # 加绝对值，对数字位置的索引进行标记前的准备
            if num <= n:
                nums[num-1] = -abs(nums[num-1])
                # 对遍历到的小于等于n的数字进行标记，标记方式为将对应索引位置变为负数
        for i in range(n):
            if nums[i]>0:
                return i+1
        return n+1
    '''class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        for j in range(1, 2 ** 31 - 1):
            if j not in nums:
                return j
                # 比较调皮的解法'''
