LeetCode41 缺失的第一个正数

缺失的第一个正数

这到题再我之前面试的时候遇见一个非常相像的，所以就拿来记录一下。

import org.junit.Test;

import java.util.Arrays;

/**
 * 缺失的第一个正数
 *
 * @author szw<szw0814 @ 1 6 3 . com> 2020/9/14
 *
 * 给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
 * 输入: [1,2,0]
 * 输出: 3

 * 输入: [3,4,-1,1]
 * 输出: 2
 */
public class findPositiveNumber {

    @Test
    public void test(){
        int[] nums = {1,2,0};
        System.out.println(firstMissingPositive(nums));
    }

    /**
     *一旦数组中出现小于等于0的数，或者是大于等于n+1的数，那么1-n中就必定有数字缺失（这里n代表数组的长度）
     */
    public int firstMissingPositive(int[] nums) {

        // 计算数组长度
        int n = nums.length;
       Arrays.sort(nums);
       // 需要想到：结果集中一定是从1开始的，如果是小于0的数不管，从1开始做对比，如果数组比rs大了。那么确是的数就找到了
        int rs = 1;
        for (int i = 0; i < n; i++) {
            if (nums[i] > rs){
                break;
            }else if(nums[i] == rs){
                rs++;
            }
        }
        return rs;
    }
}