缺失的第一个正数

给你一个未排序的整数数组 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;  
    }  
}