package Code;

import java.util.HashSet;
import java.util.Set;

public class Code41 {
    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;
        // 第一步：将所有小于等于 0 或者大于 n 的数置为 n + 1
        for(int i = 0; i< n; i++){
            if(nums[i] <= 0 || nums[i] > n){
                nums[i] = n+1;
            }
        }
        // 第二步：将出现过的正整数对应的索引位置的数置为负数
        for(int i = 0; i< n; i++){
            int num = Math.abs(nums[i]);
            if(num <= n){
                nums[num - 1] = -Math.abs(nums[num -1]);
            }
        }
        for(int i = 0; i< n; i++){
            if(nums[i] > 0){
                return i+1;
            }
        }
        return n+1;


//        Set<Integer> set = new HashSet<>();
//
//        for(int num :nums){
//            set.add(num);
//        }
//        int i = 1;
//        while(set.contains(i)){
//            i++;
//        }
//        return i;
    }
    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[]{1,2,0}));
    }
}