给你一个未排序的整数数组 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 没有出现。
解题思路
方法一：
先使用Arrays.sort()方法排序后使用二分查找，时间复杂度O(nlogn)不满足题目要求
方法二：
将数组存储到哈希集合中，后在遍历确认当前数containsKey()是否存在集合中，空间复杂度O(n)，不满足题目要求
方法三：
将数组当作哈希表存储，将每个值存到数组对应位置中，如值1存到数组0号索引中，值2存到数组1号索引中，依次类推，若是当前位置的值不是应该对应的值，则找到第一个缺失的正数，若到最后一个还没找到，则数组长度为第一个缺失的值。
解题
由于方法一、方法二不满足题目要求，使用方法三解决，附上代码
class Solution { /** * 找到数组中第一个缺失的正整数 * * @param nums 输入的整数数组 * @return 数组中第一个缺失的正整数 */ public int firstMissingPositive(int[] nums) { int len = nums.length; // 第一步：将所有不在1到len范围内的元素，以及重复的元素（通过交换到正确的位置来消除重复）进行处理 // 这个过程会确保每个位置i（0到len-1）上的元素，要么是nums[i] = i + 1，要么是nums[i] <= 0或者nums[i] > len for (int i = 0; i < len; i++) { //使用while要确保当前位置的值不用移动了，可能要移动多次while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) { swap(nums, nums[i] - 1, i); } } // 第二步：遍历数组，找到第一个不满足nums[i] = i + 1的位置 // 如果存在这样的位置，那么i + 1就是第一个缺失的正整数 // 如果遍历完整个数组都没有找到这样的位置，说明数组包含了从1到len的所有正整数，因此缺失的第一个正整数是len + 1 for (int i = 0; i < len; i++) { if (nums[i] != i + 1) { return i + 1; } } // 如果数组完整包含了从1到len的所有正整数，则返回len + 1 return len + 1; } /** * 交换数组中两个元素的位置 * * @param nums 整数数组 * @param a 要交换的第一个元素的索引 * @param b 要交换的第二个元素的索引 */ void swap(int[] nums, int a, int b) { int tmp = nums[a]; nums[a] = nums[b]; nums[b] = tmp; }
}
