一、题目描述

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？

示例 1：
输入：nums = [1,2,0]
输出：3

示例 2：
输入：nums = [3,4,-1,1]
输出：2

示例 3：
输入：nums = [7,8,9,11,12]
输出：1

提示：
0 <= nums.length <= 300
-2^31 <= nums[i] <= 2^31 - 1

二、解题思路

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

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

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

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

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