41.缺失的第一个正数

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

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

示例 1：

​

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

示例 2：

​

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

示例 3：

​

**输入：** nums = [7,8,9,11,12]
**输出：** 1

提示：

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

思路：原地哈希

class Solution {
    public int firstMissingPositive(int[] nums) {
        int i=0;
        for(i=0;i<nums.length;i++){
            //注意可能会把小于i的数字换过来，故用while循环
            //需要判断目标nums[i]所对应的哈希位置上是否已经有对应值，而不是判断当前i位置
            while(nums[i]<=nums.length&&nums[i]>0&&nums[nums[i]-1]!=nums[i]){
            //[1,1]
            // while(nums[i]<=nums.length&&nums[i]>0&&nums[i]-1!=i){
                swap(nums,nums[i]-1,i);
            }
        }
        for(i=0;i<nums.length;i++){
            if(nums[i]-1!=i)
                return i+1;
        }
        return i+1;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}