41.缺失的第一个正数

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

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

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

public static int firstMissingPositive(int[] nums) {
       int n = nums.length;
       
       for (int i = 0; i < n; i++) {
           while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
               int tmp = nums[nums[i] - 1];
               nums[nums[i] - 1] = nums[i];
               nums[i] = tmp;
           }
       }
       
       for (int i = 0; i < n; i++) {
           if (nums[i] != i + 1) {
               return i + 1;
           }
       }
       
       return n + 1;
   }

这道题之所以我一开始没有找到中间态去进行一点一点的优化，是因为我一开始的思路就是错误的，我一开始的思路是排序，但是这样明显时间复杂度是大于O（n）的，想要时间复杂度变小就得使用哈希表，虽然空间复杂度变高了，但是往这方面去优化是对的，最起码找到了一个中间态，但是还是想要空间复杂度为1，那么就要在哈希表上做文章，只要我使用原来的数组实现哈希的功能就可以了，这是最难想的，因为我必须要想到下标也可以对应。

只要让下标i对应的数据是i+1，那么就可以一眼找到第一个未出现的最小值了，实现这个功能就可以将每个数据然他进入该去的位置就好了，进行swaq交换，这个数组就变成了原地哈希表了

重要的是发现一条路走不通的时候要赶快换一条路，尽管另一条看上去也暂时实现不了，但是中间态的选择是会有优化空间的，要有嗅觉去判断是不是可以继续优化的中间态